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 |
---|---|---|---|---|---|---|
1012 | Codeforces Round 500 (Div. 1) [based on EJOI] | FINISHED | False | 9000 | 204500687 | July 30, 2018, 8:15 a.m. |
Solved$ |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
---|---|---|---|---|---|---|
( 333 ) | E | Cycle sort | PROGRAMMING | ds math | 3100 |
B'You are given an array of n positive integers a_1, a_2, ... , a_n . You can perform the following operation any number of times: select several distinct indices i_1, i_2, ... , i_k ( 1 <= i_j <= n ) and move the number standing at the position i_1 to the position i_2 , the number at the position i_2 to the position i_3 , ..., the number at the position i_k to the position i_1 . In other words, the operation cyclically shifts elements: i_1 to i_2 to ldots i_k to i_1 . For example, if you have n=4 , an array a_1=10, a_2=20, a_3=30, a_4=40 , and you choose three indices i_1=2 , i_2=1 , i_3=4 , then the resulting array would become a_1=20, a_2=40, a_3=30, a_4=10 . Your goal is to make the array sorted in non-decreasing order with the minimum number of operations. The additional constraint is that the sum of cycle lengths over all operations should be less than or equal to a number s . If it 's impossible to sort the array while satisfying that constraint, your solution should report that as well. The first line of the input contains two integers n and s ( 1 <= q n <= q 200 ,000 , 0 <= q s <= q 200 ,000 ) --the number of elements in the array and the upper bound on the sum of cycle lengths. The next line contains n integers a_1, a_2, ... , a_n --elements of the array ( 1 <= q a_i <= q 10^9 ). If it 's impossible to sort the array using cycles of total length not exceeding s , print a single number "-1" (quotes for clarity). Otherwise, print a single number q -- the minimum number of operations required to sort the array. On the next 2 cdot q lines print descriptions of operations in the order they are applied to the array. The description of i -th operation begins with a single line containing one integer k ( 1 <= k <= n ) --the length of the cycle (that is, the number of selected indices). '... |
60920 |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
---|---|---|---|---|---|---|---|---|---|---|---|
41994575 | zhou888 | E | Aug. 23, 2018, 11:17 a.m. | OK | GNU C++ | TESTS | 160 | 109 | 7680000 | 3100 | |
41148878 | Drin_E | E | Aug. 3, 2018, 7:51 a.m. | OK | GNU C++ | TESTS | 160 | 124 | 11673600 | 3100 | |
41010941 | 616156 | E | July 31, 2018, 12:36 p.m. | OK | GNU C++ | TESTS | 160 | 155 | 14745600 | 3100 | |
41961656 | dogcdt | E | Aug. 22, 2018, 9:48 a.m. | OK | GNU C++ | TESTS | 160 | 202 | 12390400 | 3100 | |
40964935 | DEGwer | E | July 30, 2018, 10:27 a.m. | OK | GNU C++ | TESTS | 160 | 358 | 72499200 | 3100 | |
41556826 | gyz_gyz | E | Aug. 13, 2018, 11:51 a.m. | OK | GNU C++ | TESTS | 160 | 405 | 41984000 | 3100 | |
41380087 | samjia2000 | E | Aug. 9, 2018, 1:37 a.m. | OK | GNU C++ | TESTS | 160 | 420 | 26316800 | 3100 | |
67068459 | MoQianXue | E | Dec. 17, 2019, 11:56 a.m. | OK | GNU C++11 | TESTS | 160 | 93 | 11161600 | 3100 | |
52624604 | SYCstudio | E | April 12, 2019, 2:03 a.m. | OK | GNU C++11 | TESTS | 160 | 124 | 13926400 | 3100 | |
53741769 | _twilight | E | May 4, 2019, 2:16 p.m. | OK | GNU C++11 | TESTS | 160 | 140 | 8396800 | 3100 | |
54506623 | WOSHIGEPACHONG2 | E | May 23, 2019, 4:25 a.m. | OK | GNU C++11 | TESTS | 160 | 140 | 8499200 | 3100 | |
52630562 | dushaolong | E | April 12, 2019, 6:48 a.m. | OK | GNU C++11 | TESTS | 160 | 140 | 13926400 | 3100 | |
44019920 | Twishkle.Aevdark | E | Oct. 9, 2018, 2:43 a.m. | OK | GNU C++11 | TESTS | 160 | 140 | 14745600 | 3100 | |
43280317 | zhouyuyang | E | Sept. 23, 2018, 4:43 a.m. | OK | GNU C++11 | TESTS | 160 | 155 | 14028800 | 3100 | |
54893779 | eriksuenderhauf | E | May 31, 2019, 11:29 p.m. | OK | GNU C++11 | TESTS | 160 | 155 | 47513600 | 3100 | |
41220265 | krijgertje | E | Aug. 4, 2018, 3:17 p.m. | OK | GNU C++11 | TESTS | 160 | 156 | 13619200 | 3100 | |
42228828 | emoairx | E | Aug. 29, 2018, 5:16 a.m. | OK | GNU C++11 | TESTS | 160 | 156 | 45056000 | 3100 | |
43081231 | zjB_shadow | E | Sept. 19, 2018, 1:58 p.m. | OK | GNU C++14 | TESTS | 160 | 62 | 15257600 | 3100 | |
41293524 | apiadu | E | Aug. 7, 2018, 5:34 a.m. | OK | GNU C++14 | TESTS | 160 | 156 | 5734400 | 3100 | |
42273697 | Elegia | E | Aug. 30, 2018, 9:54 a.m. | OK | GNU C++14 | TESTS | 160 | 156 | 10240000 | 3100 | |
43114743 | dujvet | E | Sept. 20, 2018, 1:14 p.m. | OK | GNU C++14 | TESTS | 160 | 171 | 10649600 | 3100 | |
41555472 | wakaka | E | Aug. 13, 2018, 11:01 a.m. | OK | GNU C++14 | TESTS | 160 | 186 | 13414400 | 3100 | |
41592901 | teapotd | E | Aug. 14, 2018, 3:07 p.m. | OK | GNU C++14 | TESTS | 160 | 186 | 19046400 | 3100 | |
40968344 | orbitingflea | E | July 30, 2018, 12:20 p.m. | OK | GNU C++14 | TESTS | 160 | 187 | 9420800 | 3100 | |
41335793 | DEMOPON | E | Aug. 8, 2018, 11:59 a.m. | OK | GNU C++14 | TESTS | 160 | 187 | 26624000 | 3100 | |
40995456 | consecutivelimit | E | July 31, 2018, 3:26 a.m. | OK | GNU C++14 | TESTS | 160 | 187 | 26624000 | 3100 | |
41218389 | William324 | E | Aug. 4, 2018, 2:10 p.m. | OK | GNU C++14 | TESTS | 160 | 202 | 16281600 | 3100 | |
56444859 | ITMO.cumBack | E | July 2, 2019, 6:19 p.m. | OK | GNU C++17 | TESTS | 160 | 155 | 9728000 | 3100 | |
42302206 | lixinyue | E | Aug. 31, 2018, 8:36 a.m. | OK | GNU C++17 | TESTS | 160 | 155 | 14950400 | 3100 | |
40976939 | ReaLNero1 | E | July 30, 2018, 3:57 p.m. | OK | GNU C++17 | TESTS | 160 | 155 | 14950400 | 3100 | |
40973023 | isaf27 | E | July 30, 2018, 2:04 p.m. | OK | GNU C++17 | TESTS | 160 | 155 | 14950400 | 3100 | |
41012327 | des1997 | E | July 31, 2018, 1:22 p.m. | OK | GNU C++17 | TESTS | 160 | 171 | 14950400 | 3100 | |
40997278 | ykn1 | E | July 31, 2018, 4:56 a.m. | OK | GNU C++17 | TESTS | 160 | 171 | 14950400 | 3100 | |
41103754 | kczno1 | E | Aug. 2, 2018, 2:40 a.m. | OK | GNU C++17 | TESTS | 160 | 171 | 16793600 | 3100 | |
40966430 | dacin21 | E | July 30, 2018, 10:40 a.m. | OK | GNU C++17 | TESTS | 160 | 202 | 20377600 | 3100 | |
60462980 | saketh | E | Sept. 12, 2019, 10:09 p.m. | OK | GNU C++17 | TESTS | 160 | 217 | 15769600 | 3100 | |
56818716 | Smaug | E | July 10, 2019, 9:14 p.m. | OK | GNU C++17 | TESTS | 160 | 218 | 31539200 | 3100 | |
41065372 | mmaxio | E | July 31, 2018, 6:35 p.m. | OK | Java 8 | TESTS | 160 | 405 | 18739200 | 3100 |
Back to search problems