Codeforces Round 1005 (Div. 2)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
2064 Codeforces Round 1005 (Div. 2) FINISHED False 7200 36689123 Feb. 16, 2025, 2:35 p.m.

Problems

Solved
Index
Name
Type
Tags
Community Tag
Rating
( 1456 ) E Mycraft Sand Sort PROGRAMMING combinatorics data structures dsu

Steve has a permutation(^{\text{∗}}) (p) and an array (c), both of length (n). Steve wishes to sort the permutation (p). Steve has an infinite supply of coloured sand blocks, and using them he discovered a physics-based way to sort an array of numbers called gravity sort. Namely, to perform gravity sort on (p), Steve will do the following: For all (i) such that (1 \le i \le n), place a sand block of color (c_i) in position ((i, j)) for all (j) where (1 \le j \le p_i). Here, position ((x, y)) denotes a cell in the (x)-th row from the top and (y)-th column from the left. Apply downwards gravity to the array, so that all sand blocks fall as long as they can fall. Alex looks at Steve's sand blocks after performing gravity sort and wonders how many pairs of arrays ((p',c')) where (p') is a permutation would have resulted in the same layout of sand. Note that the original pair of arrays ((p, c)) will always be counted. Please calculate this for Alex. As this number could be large, output it modulo (998\,244\,353). (^{\text{∗}})A permutation of length (n) is an array consisting of (n) distinct integers from (1) to (n) in arbitrary order. For example, (2,3,1,5,4) is a permutation, but (1,2,2) is not a permutation ((2) appears twice in the array), and (1,3,4) is also not a permutation ((n=3) but there is a (4) in the array). The first line contains an integer (t) ((1 \le t \le 10^4)) — the number of test cases. The first line of each testcase contains an integer (n) ((1 \le n \le 2 \cdot 10^5)) — the lengths of the arrays. The second line of each testcase contains (n) distinct integers (p_1,p_2,\ldots,p_n) ((1 \le p_i \le n)) — the elements of (p). The following line contains (n) integers (c_1,c_2,\ldots,c_n) ((1 \le c_i \le n)) — the elements of (c). The sum of (n) across all testcases doe

Tutorials

Codeforces Round 1005 (Div. 2) Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
306471371 11490DX E Feb. 17, 2025, 2:31 a.m. OK C++17 (GCC 7-32) TESTS 41 140 5632000
306427992 gs17005 E Feb. 16, 2025, 4:33 p.m. OK C++17 (GCC 7-32) TESTS 40 155 10444800
306432579 P.V.Sekhar E Feb. 16, 2025, 5:10 p.m. OK C++17 (GCC 7-32) TESTS 40 155 10547200
306440624 Linear_B E Feb. 16, 2025, 6:06 p.m. OK C++17 (GCC 7-32) TESTS 41 156 6451200
306424705 xiaoyezi2007 E Feb. 16, 2025, 4:26 p.m. OK C++17 (GCC 7-32) TESTS 40 156 6451200
306435222 Code937 E Feb. 16, 2025, 5:26 p.m. OK C++17 (GCC 7-32) TESTS 41 156 48128000
306482126 3owo3 E Feb. 17, 2025, 5:23 a.m. OK C++17 (GCC 7-32) TESTS 41 171 5632000
306470942 LaDeX E Feb. 17, 2025, 2:23 a.m. OK C++17 (GCC 7-32) TESTS 41 171 6451200
306432369 CrispyLobster E Feb. 16, 2025, 5:09 p.m. OK C++17 (GCC 7-32) TESTS 40 171 8908800
306428628 fanfly E Feb. 16, 2025, 4:34 p.m. OK C++17 (GCC 7-32) TESTS 40 171 8908800
306469632 ji_114514 E Feb. 17, 2025, 1:53 a.m. OK C++20 (GCC 13-64) TESTS 41 109 2048000
306477208 MintCat E Feb. 17, 2025, 4:13 a.m. OK C++20 (GCC 13-64) TESTS 41 124 1228800
306481672 adam.jq.xu E Feb. 17, 2025, 5:17 a.m. OK C++20 (GCC 13-64) TESTS 41 124 11366400
306435852 scanner E Feb. 16, 2025, 5:30 p.m. OK C++20 (GCC 13-64) TESTS 41 139 6041600
306478527 Zhangxuyang E Feb. 17, 2025, 4:35 a.m. OK C++20 (GCC 13-64) TESTS 41 140 5632000
306481805 www.com E Feb. 17, 2025, 5:19 a.m. OK C++20 (GCC 13-64) TESTS 41 140 5939200
306481256 www.com E Feb. 17, 2025, 5:13 a.m. OK C++20 (GCC 13-64) TESTS 41 140 6041600
306481228 LuHOvO E Feb. 17, 2025, 5:13 a.m. OK C++20 (GCC 13-64) TESTS 41 140 8089600
306435780 PaperCloud E Feb. 16, 2025, 5:29 p.m. OK C++20 (GCC 13-64) TESTS 41 140 17715200
306475366 haozzZ E Feb. 17, 2025, 3:44 a.m. OK C++20 (GCC 13-64) TESTS 41 155 14028800
306476167 Brilliance_Z E Feb. 17, 2025, 3:56 a.m. OK C++23 (GCC 14-64, msys2) TESTS 41 109 6451200
306461829 MoamenZ E Feb. 16, 2025, 10:14 p.m. OK C++23 (GCC 14-64, msys2) TESTS 41 109 9625600
306446863 jiangly E Feb. 16, 2025, 6:57 p.m. OK C++23 (GCC 14-64, msys2) TESTS 41 124 4812800
306439616 415411 E Feb. 16, 2025, 5:58 p.m. OK C++23 (GCC 14-64, msys2) TESTS 41 124 9625600
306473851 Legendary_Noxus E Feb. 17, 2025, 3:17 a.m. OK C++23 (GCC 14-64, msys2) TESTS 41 124 14643200
306458581 Auchenai01 E Feb. 16, 2025, 9:16 p.m. OK C++23 (GCC 14-64, msys2) TESTS 41 125 5632000
306424036 tfg E Feb. 16, 2025, 4:25 p.m. OK C++23 (GCC 14-64, msys2) TESTS 40 140 4096000
306458372 Auchenai01 E Feb. 16, 2025, 9:13 p.m. OK C++23 (GCC 14-64, msys2) TESTS 41 140 5632000
306426602 qfl-zzz E Feb. 16, 2025, 4:30 p.m. OK C++23 (GCC 14-64, msys2) TESTS 40 140 9728000
306444618 ALAov E Feb. 16, 2025, 6:36 p.m. OK C++23 (GCC 14-64, msys2) TESTS 41 155 16486400
306475920 wddd E Feb. 17, 2025, 3:52 a.m. OK Java 21 TESTS 41 327 1331200
306433514 shardulisgapryongkim E Feb. 16, 2025, 5:16 p.m. OK Java 21 TESTS 41 937 8499200
306472587 srujan_bunny E Feb. 17, 2025, 2:54 a.m. OK Java 21 TESTS 41 1030 50176000
306424732 Svyat E Feb. 16, 2025, 4:26 p.m. OK Kotlin 1.9 TESTS 40 1030 26214400
306423386 Eunha E Feb. 16, 2025, 4:24 p.m. OK PyPy 3-64 TESTS 40 686 64921600
306483323 Ezru1 E Feb. 17, 2025, 5:38 a.m. OK PyPy 3-64 TESTS 41 812 43520000
306434349 ow3nL E Feb. 16, 2025, 5:20 p.m. OK PyPy 3-64 TESTS 41 2077 48742400
306431378 hexagoning E Feb. 16, 2025, 5:06 p.m. OK Python 3 TESTS 40 1233 69017600

remove filters

Back to search problems