Codeforces Round 500 (Div. 1) [based on EJOI]

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.

Problems

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). '...

Tutorials

60920

Submissions

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

remove filters

Back to search problems