Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine))

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
1558 Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine)) FINISHED False 9000 102007499 Aug. 24, 2021, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 3304 ) C Bottom-Tier Reversals PROGRAMMING constructive algorithms greedy 2000

B"You have a permutation: an array a = [a_1, a_2, ldots, a_n] of distinct integers from 1 to n . The length of the permutation n is odd. You need to sort the permutation in increasing order. In one step, you can choose any prefix of the permutation with an odd length and reverse it. Formally, if a = [a_1, a_2, ldots, a_n] , you can choose any odd integer p between 1 and n , inclusive, and set a to [a_p, a_{p-1}, ldots, a_1, a_{p+1}, a_{p+2}, ldots, a_n] . Find a way to sort a using no more than frac{5n}{2} reversals of the above kind, or determine that such a way doesn't exist. The number of reversals doesn't have to be minimized. Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 100 ). Description of the test cases follows. The first line of each test case contains a single integer n ( 3 <= n <= 2021 ; n is odd) -- the length of the permutation. The second line contains n distinct integers a_1, a_2, ldots, a_n ( 1 <= a_i <= n ) -- the permutation itself. It is guaranteed that the sum of n over all test cases does not exceed 2021 . For each test case, if it's impossible to sort the given permutation in at most frac{5n}{2} reversals, print a single integer -1 . Otherwise, print an integer m ( 0 <= m <= frac{5n}{2} ), denoting the number of reversals in your sequence of steps, followed by m integers p_i ( 1 <= p_i <= n ; p_i is odd), denoting the lengths of the prefixes of a to be reversed, in chronological order. Note that m doesn't have to be minimized. If there are multiple answers, print any. In the first test case, the permutation is already sorted. Any even number of reversals of the length 3 prefix doesn't change that fact. In the second test case, after reversing the prefix of length 3 the per"...

Tutorials

Codeforces Round #740 Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
126858403 hos.lyric C Aug. 24, 2021, 3:01 p.m. OK D TESTS 51 31 9011200 2000
126863479 Gassa C Aug. 24, 2021, 3:10 p.m. OK D TESTS 51 31 9011200 2000
126931216 wanghaoze C Aug. 25, 2021, 4:07 a.m. OK GNU C++14 TESTS 51 30 3788800 2000
126897951 skicean C Aug. 24, 2021, 4:42 p.m. OK GNU C++14 TESTS 51 30 3788800 2000
126881648 comld C Aug. 24, 2021, 3:53 p.m. OK GNU C++14 TESTS 51 30 3788800 2000
126971441 walk_alone C Aug. 25, 2021, 1:15 p.m. OK GNU C++14 TESTS 51 30 3788800 2000
126902698 dp_everyday C Aug. 24, 2021, 4:58 p.m. OK GNU C++14 TESTS 51 30 3891200 2000
126882808 Lily C Aug. 24, 2021, 3:56 p.m. OK GNU C++14 TESTS 51 30 3993600 2000
126871542 idxcalcal C Aug. 24, 2021, 3:28 p.m. OK GNU C++14 TESTS 51 30 5017600 2000
126872032 Katou_Umi C Aug. 24, 2021, 3:29 p.m. OK GNU C++14 TESTS 51 30 5734400 2000
126877033 yzyyylx C Aug. 24, 2021, 3:42 p.m. OK GNU C++14 TESTS 51 30 67993600 2000
126922480 xuanxuan001 C Aug. 25, 2021, 12:50 a.m. OK GNU C++14 TESTS 51 31 3686400 2000
126901056 DeMen100ns C Aug. 24, 2021, 4:52 p.m. OK GNU C++17 TESTS 51 15 3788800 2000
126920983 shygo_cmll01 C Aug. 24, 2021, 11:50 p.m. OK GNU C++17 TESTS 51 30 3686400 2000
126983269 vujica.nikola07 C Aug. 25, 2021, 3:35 p.m. OK GNU C++17 TESTS 51 30 3788800 2000
126875830 Roundgod C Aug. 24, 2021, 3:39 p.m. OK GNU C++17 TESTS 51 30 3891200 2000
126879455 ACCOUNT_FOR_BAD_ROUNDS C Aug. 24, 2021, 3:48 p.m. OK GNU C++17 TESTS 51 30 3891200 2000
126933105 forceac C Aug. 25, 2021, 4:43 a.m. OK GNU C++17 TESTS 51 30 3993600 2000
126894421 islingr C Aug. 24, 2021, 4:30 p.m. OK GNU C++17 TESTS 51 30 3993600 2000
126909330 egorhs19 C Aug. 24, 2021, 6:18 p.m. OK GNU C++17 TESTS 51 30 3993600 2000
126916174 s_jaskaran_s C Aug. 24, 2021, 8:28 p.m. OK GNU C++17 TESTS 51 30 3993600 2000
126967999 Temirulan C Aug. 25, 2021, 12:27 p.m. OK GNU C++17 TESTS 51 30 3993600 2000
126859482 maroonrk C Aug. 24, 2021, 3:03 p.m. OK GNU C++17 (64) TESTS 51 15 4505600 2000
126894610 Ripiaun C Aug. 24, 2021, 4:31 p.m. OK GNU C++17 (64) TESTS 51 30 4403200 2000
127009358 dingdingsb C Aug. 26, 2021, 2 a.m. OK GNU C++17 (64) TESTS 51 30 4403200 2000
126972229 Ripiaun C Aug. 25, 2021, 1:26 p.m. OK GNU C++17 (64) TESTS 51 30 4403200 2000
126894530 Anonymous_Noob C Aug. 24, 2021, 4:31 p.m. OK GNU C++17 (64) TESTS 51 30 4403200 2000
126892610 Sorting C Aug. 24, 2021, 4:24 p.m. OK GNU C++17 (64) TESTS 51 30 4403200 2000
126890274 CrayonKe C Aug. 24, 2021, 4:18 p.m. OK GNU C++17 (64) TESTS 51 30 4403200 2000
126884315 olphe C Aug. 24, 2021, 4 p.m. OK GNU C++17 (64) TESTS 51 30 4403200 2000
126883829 udon1206 C Aug. 24, 2021, 3:59 p.m. OK GNU C++17 (64) TESTS 51 30 4403200 2000
126883441 snuphy C Aug. 24, 2021, 3:58 p.m. OK GNU C++17 (64) TESTS 51 30 4403200 2000
126871018 clyring C Aug. 24, 2021, 3:27 p.m. OK Haskell TESTS 51 342 11673600 2000
126984953 Ste C Aug. 25, 2021, 3:55 p.m. OK Java 11 TESTS 51 187 24371200 2000
126881018 Sohomot_Vai C Aug. 24, 2021, 3:52 p.m. OK Java 11 TESTS 51 202 24371200 2000
126963494 dalt C Aug. 25, 2021, 11:25 a.m. OK Java 11 TESTS 51 202 25497600 2000
126877371 insert_cool_handle C Aug. 24, 2021, 3:42 p.m. OK Java 11 TESTS 51 218 24678400 2000
126995768 Matheolympiade C Aug. 25, 2021, 6:31 p.m. OK Java 11 TESTS 51 249 25088000 2000
126890168 pulkit1411 C Aug. 24, 2021, 4:17 p.m. OK Java 11 TESTS 51 265 42598400 2000
126884744 YahiaSherif C Aug. 24, 2021, 4:02 p.m. OK Java 8 TESTS 51 140 20992000 2000
126861519 JHope C Aug. 24, 2021, 3:07 p.m. OK Java 8 TESTS 51 140 20992000 2000
126861338 SecondThread C Aug. 24, 2021, 3:06 p.m. OK Java 8 TESTS 51 171 21094400 2000
126890953 Hakiobo C Aug. 24, 2021, 4:20 p.m. OK Kotlin TESTS 51 156 22323200 2000
126870524 LeoPro C Aug. 24, 2021, 3:26 p.m. OK Kotlin TESTS 51 187 24064000 2000
126864416 arvindf232 C Aug. 24, 2021, 3:12 p.m. OK Kotlin TESTS 51 327 23859200 2000
126883271 azukun C Aug. 24, 2021, 3:58 p.m. OK .NET Core C# TESTS 51 108 12083200 2000
126891085 eSeF_ C Aug. 24, 2021, 4:20 p.m. OK .NET Core C# TESTS 51 109 11980800 2000
126861117 mban259 C Aug. 24, 2021, 3:06 p.m. OK .NET Core C# TESTS 51 109 12288000 2000
126880149 keymoon C Aug. 24, 2021, 3:49 p.m. OK .NET Core C# TESTS 51 124 12288000 2000
126882077 eepsilon C Aug. 24, 2021, 3:54 p.m. OK PyPy 3 TESTS 51 140 23449600 2000
126886104 misorin C Aug. 24, 2021, 4:05 p.m. OK PyPy 3 TESTS 51 140 23552000 2000
126879474 conqueror_of_tourist C Aug. 24, 2021, 3:48 p.m. OK PyPy 3 TESTS 51 140 23654400 2000
126892002 titia C Aug. 24, 2021, 4:23 p.m. OK PyPy 3 TESTS 51 140 26316800 2000
126864550 asdsasd C Aug. 24, 2021, 3:13 p.m. OK PyPy 3 TESTS 51 155 24985600 2000
126893493 Kiri8128 C Aug. 24, 2021, 4:27 p.m. OK PyPy 3 TESTS 51 436 33280000 2000
126863384 huikang C Aug. 24, 2021, 3:10 p.m. OK PyPy 3 TESTS 51 452 33484800 2000
126890893 chinerist C Aug. 24, 2021, 4:19 p.m. OK PyPy 3 TESTS 51 468 37273600 2000
126893813 apilat C Aug. 24, 2021, 4:28 p.m. OK Rust TESTS 51 46 3891200 2000
126880484 sansen C Aug. 24, 2021, 3:50 p.m. OK Rust TESTS 51 46 4198400 2000

remove filters

Back to search problems