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. |
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'... |
Codeforces Global Round 25 Editorial |
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 |
Back to search problems