Codeforces Round 656 (Div. 3)

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
1385 Codeforces Round 656 (Div. 3) FINISHED False 8100 142356311 July 17, 2020, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 1583 ) G Columns Swaps PROGRAMMING 2-sat dfs and similar ds graphs implementation 2300

B"You are given a table a of size 2 x n (i.e. two rows and n columns) consisting of integers from 1 to n . In one move, you can choose some column j ( 1 <= j <= n ) and swap values a_{1, j} and a_{2, j} in it. Each column can be chosen no more than once. Your task is to find the minimum number of moves required to obtain permutations of size n in both first and second rows of the table or determine if it is impossible to do that. You have to answer t independent test cases. Recall that the permutation of size n is such an array of size n that contains each integer from 1 to n exactly once (the order of elements doesn't matter). The first line of the input contains one integer t ( 1 <= t <= 2 cdot 10^4 ) -- the number of test cases. Then t test cases follow. The first line of the test case contains one integer n ( 1 <= n <= 2 cdot 10^5 ) -- the number of columns in the table. The second line of the test case contains n integers a_{1, 1}, a_{1, 2}, ... , a_{1, n} ( 1 <= a_{1, i} <= n ), where a_{1, i} is the i -th element of the first row of the table. The third line of the test case contains n integers a_{2, 1}, a_{2, 2}, ... , a_{2, n} ( 1 <= a_{2, i} <= n ), where a_{2, i} is the i -th element of the second row of the table. It is guaranteed that the sum of n does not exceed 2 cdot 10^5 ( sum n <= 2 cdot 10^5 ). For each test case print the answer: -1 if it is impossible to obtain permutation of size n in both first and the second rows of the table, or one integer k in the first line, where k is the minimum number of moves required to obtain permutations in both rows, and k distinct integers pos_1, pos_2, ... , pos_k in the second line ( 1 <= pos_i <= n ) in any order -- indices of columns in which you need to swap "...

Tutorials

Codeforces Round #656 (Div. 3) Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
87142582 Gassa G July 17, 2020, 4:03 p.m. OK D TESTS 35 139 18227200 2300
87163841 DarkoLoveRuby G July 17, 2020, 5:07 p.m. OK GNU C++11 TESTS 35 124 11878400 2300
87139267 dysyn1314 G July 17, 2020, 3:56 p.m. OK GNU C++11 TESTS 35 124 16384000 2300
87192417 xwd456 G July 18, 2020, 3:34 a.m. OK GNU C++11 TESTS 35 124 24166400 2300
87183006 amr962 G July 17, 2020, 10:01 p.m. OK GNU C++11 TESTS 35 140 10240000 2300
87186673 tpaaaa G July 18, 2020, 12:41 a.m. OK GNU C++11 TESTS 35 140 24268800 2300
87185049 Ogiso G July 17, 2020, 11:14 p.m. OK GNU C++11 TESTS 35 140 48332800 2300
87154074 cppascalinux G July 17, 2020, 4:32 p.m. OK GNU C++11 TESTS 35 155 21913600 2300
87191693 xwd456 G July 18, 2020, 3:17 a.m. OK GNU C++11 TESTS 35 171 17203200 2300
87162511 alocytus G July 17, 2020, 4:58 p.m. OK GNU C++11 TESTS 35 171 19968000 2300
87168935 serotonin G July 17, 2020, 5:58 p.m. OK GNU C++11 TESTS 35 171 24371200 2300
87173537 xsc G July 17, 2020, 6:51 p.m. OK GNU C++14 TESTS 35 140 10342400 2300
87128130 dlalswp25 G July 17, 2020, 3:34 p.m. OK GNU C++14 TESTS 35 155 11776000 2300
87146999 ranwen3 G July 17, 2020, 4:14 p.m. OK GNU C++14 TESTS 35 202 10956800 2300
87163757 zpzpzp G July 17, 2020, 5:07 p.m. OK GNU C++14 TESTS 35 202 13721600 2300
87183109 Potassium G July 17, 2020, 10:05 p.m. OK GNU C++14 TESTS 35 202 17612800 2300
87186239 alleviatedRules G July 18, 2020, 12:17 a.m. OK GNU C++14 TESTS 35 217 14028800 2300
87148104 Drice G July 17, 2020, 4:17 p.m. OK GNU C++14 TESTS 35 218 20480000 2300
87182703 idontreallyknow G July 17, 2020, 9:53 p.m. OK GNU C++14 TESTS 35 233 21913600 2300
87170674 vrobyka G July 17, 2020, 6:16 p.m. OK GNU C++14 TESTS 35 249 18944000 2300
87177347 yatink2000 G July 17, 2020, 7:48 p.m. OK GNU C++14 TESTS 35 249 21913600 2300
87158781 LayCurse G July 17, 2020, 4:45 p.m. OK GNU C++17 TESTS 35 62 14643200 2300
87157041 Marcythm G July 17, 2020, 4:41 p.m. OK GNU C++17 TESTS 35 77 20480000 2300
87139436 Austin_Griffin2 G July 17, 2020, 3:56 p.m. OK GNU C++17 TESTS 35 140 9523200 2300
87148870 EndRay G July 17, 2020, 4:18 p.m. OK GNU C++17 TESTS 35 155 9420800 2300
87178652 sayeedt G July 17, 2020, 8:12 p.m. OK GNU C++17 TESTS 35 155 10035200 2300
87157732 gyuni G July 17, 2020, 4:42 p.m. OK GNU C++17 TESTS 35 155 10547200 2300
87176268 alykov G July 17, 2020, 7:30 p.m. OK GNU C++17 TESTS 35 155 10854400 2300
87193334 AvinashKartik G July 18, 2020, 3:55 a.m. OK GNU C++17 TESTS 35 155 31436800 2300
87170112 LUL____SEPLED1305 G July 17, 2020, 6:11 p.m. OK GNU C++17 TESTS 35 156 10240000 2300
87159588 Autobus G July 17, 2020, 4:47 p.m. OK GNU C++17 TESTS 35 171 9932800 2300
87192052 Eureka17 G July 18, 2020, 3:26 a.m. OK GNU C++17 (64) TESTS 35 186 35532800 2300
87140830 universe- G July 17, 2020, 3:59 p.m. OK GNU C++17 (64) TESTS 35 187 16998400 2300
87147723 ALILILILILI-KHAN G July 17, 2020, 4:16 p.m. OK GNU C++17 (64) TESTS 35 187 38195200 2300
87152537 grand_zeno G July 17, 2020, 4:28 p.m. OK GNU C++17 (64) TESTS 35 202 17715200 2300
87137600 tute7627 G July 17, 2020, 3:52 p.m. OK GNU C++17 (64) TESTS 35 202 32460800 2300
87149875 SorahISA G July 17, 2020, 4:21 p.m. OK GNU C++17 (64) TESTS 35 202 32563200 2300
87172051 smax G July 17, 2020, 6:32 p.m. OK GNU C++17 (64) TESTS 35 202 33792000 2300
87125565 risujiroh G July 17, 2020, 3:29 p.m. OK GNU C++17 (64) TESTS 35 217 26419200 2300
87146023 Hyado G July 17, 2020, 4:11 p.m. OK GNU C++17 (64) TESTS 35 218 27238400 2300
87150025 micheeeeell G July 17, 2020, 4:21 p.m. OK GNU C++17 (64) TESTS 35 233 31641600 2300
87162889 meooow G July 17, 2020, 5:01 p.m. OK Go TESTS 35 249 77414400 2300
87136718 uwi G July 17, 2020, 3:50 p.m. OK Java 11 TESTS 35 436 53555200 2300
87194122 Richard727 G July 18, 2020, 4:14 a.m. OK Java 11 TESTS 35 498 58880000 2300
87194340 Richard727 G July 18, 2020, 4:20 a.m. OK Java 11 TESTS 35 545 58777600 2300
87172902 out_of_the_box G July 17, 2020, 6:43 p.m. OK Java 8 TESTS 35 608 52838400 2300
87181645 MagentaCobra G July 17, 2020, 9:22 p.m. OK Java 8 TESTS 35 717 90726400 2300
87139891 MagentaCobra G July 17, 2020, 3:57 p.m. OK Java 8 TESTS 35 748 90726400 2300
87191316 flyman3046 G July 18, 2020, 3:08 a.m. OK Java 8 TESTS 35 1075 183603200 2300
87155238 CF_is_my_GF G July 17, 2020, 4:36 p.m. OK Java 8 TESTS 35 1138 126361600 2300
87156511 Hakiobo G July 17, 2020, 4:39 p.m. OK Kotlin TESTS 35 233 23654400 2300
87151830 ekaerovets G July 17, 2020, 4:26 p.m. OK Kotlin TESTS 35 342 27340800 2300
87126278 Tlatoani G July 17, 2020, 3:30 p.m. OK Kotlin TESTS 35 405 49152000 2300
87135339 koboshi G July 17, 2020, 3:47 p.m. OK Kotlin TESTS 35 608 81100800 2300
87169240 pichulia G July 17, 2020, 6:01 p.m. OK MS C++ 2017 TESTS 35 342 40345600 2300
87171211 youx G July 17, 2020, 6:22 p.m. OK MS C++ 2017 TESTS 35 374 35737600 2300
87161824 DavitMarg G July 17, 2020, 4:54 p.m. OK MS C++ 2017 TESTS 35 451 22835200 2300
87153585 Gravekper G July 17, 2020, 4:31 p.m. OK MS C++ 2017 TESTS 35 483 14233600 2300
87167839 sh1194 G July 17, 2020, 5:45 p.m. OK PyPy 2 TESTS 35 233 47001600 2300
87147471 pajenegod G July 17, 2020, 4:15 p.m. OK PyPy 2 TESTS 35 264 47001600 2300
87167618 sh1194 G July 17, 2020, 5:43 p.m. OK PyPy 2 TESTS 35 265 47001600 2300
87197745 mkawa2 G July 18, 2020, 5:38 a.m. OK PyPy 3 TESTS 35 889 133529600 2300
87176029 throwawayatcoder G July 17, 2020, 7:26 p.m. OK PyPy 3 TESTS 35 1060 126566400 2300
87144343 robostac G July 17, 2020, 4:07 p.m. OK Rust TESTS 35 109 14438400 2300
87194312 sansen G July 18, 2020, 4:19 a.m. OK Rust TESTS 35 358 47513600 2300

remove filters

Back to search problems