Codeforces Global Round 25

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
1951 Codeforces Global Round 25 FINISHED False 10800 19409099 April 6, 2024, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 767 ) F Inversion Composition PROGRAMMING binary search constructive algorithms data structures greedy

B'You are given a permutation p of size n , as well as a non-negative integer k . You need to construct a permutation q of size n such that operatorname{inv}(q) + operatorname{inv}(q cdot p) = k {}^ dagger {}^ ddagger , or determine if it is impossible to do so. {}^ dagger For two permutations p and q of the same size n , the permutation w = q cdot p is such that w_i = q_{p_i} for all 1 <= i <= n . {}^ ddagger For a permutation p of size n , the function operatorname{inv}(p) returns the number of inversions of p , i.e. the number of pairs of indices 1 <= i < j <= n such that p_i > p_j . Each test contains multiple test cases. The first line contains an integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains two integers n and k ( 1 <= n <= 3 cdot 10^5, 0 <= k <= n(n - 1) ) -- the size of p and the target number of inversions. The second line of each test case contains n integers p_1, p_2, ldots, p_n ( 1 <= p_i <= n , p_i 's are pairwise distinct) -- the given permutation p . It is guaranteed that the sum of n over all test cases does not exceed 3 cdot 10^5 . For each test case, print on one line "YES" if there exists a permutation q that satisfies the given condition, or "NO" if there is no such permutation. If the answer is "YES", on the second line, print n integers q_1, q_2, ldots, q_n that represent such a satisfactory permutation q . If there are multiple such q 's, print any of them. In the first test case, we have q cdot p = [2, 1, 3] , operatorname{inv}(q) = 3 , and operatorname{inv}(q cdot p) = 1 . In the fourth test case, we have q cdot p = [9, 1, 8, 5, 7, 6, 4, 3, 2] , operatorname{inv}(q) = 24 , and'...

Tutorials

Codeforces Global Round 25 Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
255359365 Imdie F April 6, 2024, 5:33 p.m. OK C++14 (GCC 6-32) TESTS 98 202 3686400
255356352 HHH666666 F April 6, 2024, 5:26 p.m. OK C++14 (GCC 6-32) TESTS 98 202 3686400
255395877 Celebrate F April 6, 2024, 11:59 p.m. OK C++14 (GCC 6-32) TESTS 98 234 4812800
255403156 Iratis F April 7, 2024, 2:14 a.m. OK C++14 (GCC 6-32) TESTS 98 312 14540800
255391246 fast_photon F April 6, 2024, 10:39 p.m. OK C++14 (GCC 6-32) TESTS 98 531 19251200
255409840 Legitimity F April 7, 2024, 3:58 a.m. OK C++17 (GCC 7-32) TESTS 98 124 8192000
255396596 registeretsiger F April 7, 2024, 12:13 a.m. OK C++17 (GCC 7-32) TESTS 98 156 2355200
255372742 kimoyami F April 6, 2024, 7:24 p.m. OK C++17 (GCC 7-32) TESTS 98 156 2355200
255363617 NTT F April 6, 2024, 6:19 p.m. OK C++17 (GCC 7-32) TESTS 98 156 6758400
255376037 Mtaylor F April 6, 2024, 7:51 p.m. OK C++17 (GCC 7-32) TESTS 98 171 5222400
255394889 Dimitrovsd F April 6, 2024, 11:42 p.m. OK C++17 (GCC 7-32) TESTS 98 171 6041600
255358917 LuCpp F April 6, 2024, 5:32 p.m. OK C++17 (GCC 7-32) TESTS 98 187 2355200
255365003 _Fake4Fun F April 6, 2024, 6:26 p.m. OK C++17 (GCC 7-32) TESTS 98 187 4915200
255372182 arnold518 F April 6, 2024, 7:18 p.m. OK C++17 (GCC 7-32) TESTS 98 202 3686400
255359369 Sorting F April 6, 2024, 5:33 p.m. OK C++17 (GCC 7-32) TESTS 98 202 7475200
255367736 beiyuli F April 6, 2024, 6:43 p.m. OK C++20 (GCC 13-64) TESTS 98 124 2355200
255378554 BalintR F April 6, 2024, 8:14 p.m. OK C++20 (GCC 13-64) TESTS 98 124 2457600
255398102 ab1aze F April 7, 2024, 12:41 a.m. OK C++20 (GCC 13-64) TESTS 98 124 6041600
255398247 Lyreqwq F April 7, 2024, 12:44 a.m. OK C++20 (GCC 13-64) TESTS 98 125 2355200
255403190 enslaved F April 7, 2024, 2:14 a.m. OK C++20 (GCC 13-64) TESTS 98 139 5427200
255398631 happydef F April 7, 2024, 12:51 a.m. OK C++20 (GCC 13-64) TESTS 98 139 79360000
255359855 fr200110217102 F April 6, 2024, 5:34 p.m. OK C++20 (GCC 13-64) TESTS 98 140 2355200
255414454 gqf123 F April 7, 2024, 4:55 a.m. OK C++20 (GCC 13-64) TESTS 98 140 3686400
255407564 LinkWish F April 7, 2024, 3:26 a.m. OK C++20 (GCC 13-64) TESTS 98 140 4915200
255395531 1RONMAN F April 6, 2024, 11:53 p.m. OK C++20 (GCC 13-64) TESTS 98 140 5427200
255378423 rainboy F April 6, 2024, 8:13 p.m. OK GNU C11 TESTS 98 1327 4915200
255387725 hxu10 F April 6, 2024, 9:50 p.m. OK PyPy 3-64 TESTS 98 437 56217600
255356302 dyppp F April 6, 2024, 5:25 p.m. OK PyPy 3-64 TESTS 98 609 54272000
255367769 ngtkana F April 6, 2024, 6:44 p.m. OK Rust 2021 TESTS 98 343 35635200

remove filters

Back to search problems