Task: | Käännöt |
Sender: | cppbetter |
Submission time: | 2023-11-01 18:58:05 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | 65 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 13 |
#2 | ACCEPTED | 19 |
#3 | ACCEPTED | 33 |
#4 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1 | details |
#2 | ACCEPTED | 0.00 s | 1 | details |
#3 | ACCEPTED | 0.00 s | 1 | details |
#4 | ACCEPTED | 0.00 s | 1 | details |
#5 | ACCEPTED | 0.00 s | 1 | details |
#6 | ACCEPTED | 0.00 s | 2 | details |
#7 | ACCEPTED | 0.00 s | 2 | details |
#8 | ACCEPTED | 0.00 s | 2 | details |
#9 | ACCEPTED | 0.00 s | 2 | details |
#10 | ACCEPTED | 0.00 s | 2 | details |
#11 | ACCEPTED | 0.01 s | 2 | details |
#12 | ACCEPTED | 0.01 s | 2 | details |
#13 | ACCEPTED | 0.01 s | 2 | details |
#14 | ACCEPTED | 0.01 s | 2 | details |
#15 | ACCEPTED | 0.00 s | 2 | details |
#16 | ACCEPTED | 0.02 s | 2 | details |
#17 | ACCEPTED | 0.00 s | 3 | details |
#18 | ACCEPTED | 0.00 s | 3 | details |
#19 | ACCEPTED | 0.01 s | 3 | details |
#20 | ACCEPTED | 0.01 s | 3 | details |
#21 | ACCEPTED | 0.01 s | 3 | details |
#22 | ACCEPTED | 0.01 s | 3 | details |
#23 | ACCEPTED | 0.01 s | 3 | details |
#24 | ACCEPTED | 0.01 s | 3 | details |
#25 | ACCEPTED | 0.01 s | 3 | details |
#26 | ACCEPTED | 0.00 s | 4 | details |
#27 | WRONG ANSWER | 0.00 s | 4 | details |
#28 | WRONG ANSWER | 0.00 s | 4 | details |
#29 | WRONG ANSWER | 0.00 s | 4 | details |
#30 | WRONG ANSWER | 0.00 s | 4 | details |
#31 | WRONG ANSWER | 0.00 s | 4 | details |
#32 | WRONG ANSWER | 0.00 s | 4 | details |
#33 | WRONG ANSWER | 0.00 s | 4 | details |
#34 | WRONG ANSWER | 0.00 s | 4 | details |
Code
#include <iostream> #include <vector> #include <array> #include <algorithm> //#define GENANS using namespace std; vector<int> list; vector<int> op; int n, k; void swp2(int l) { swap(list[l], list[l + 1]); } void swp3(int l) { swap(list[l], list[l + 2]); } void swp4(int l) { swap(list[l], list[l + 3]); swap(list[l+1], list[l + 2]); } void swp5(int l) { swap(list[l], list[l + 4]); swap(list[l + 1], list[l + 3]); } struct Solution { int a, b, c, d; vector<int> ops; }; vector<Solution> solutions; bool slv() { // Get last 4 numbs int a, b, c, d; a = list[n - 4] - n + 4; b = list[n - 3] - n + 4; c = list[n - 2] - n + 4; d = list[n - 1] - n + 4; for (auto s : solutions) { if (s.a == a && s.b == b && s.c == c && s.d == d) { for (auto o : s.ops) { op.push_back(o + n); swp4(o - 1 + n); } return true; } } #ifdef GENANS // reverse of the operetions is the solution cout << "solutions.emplace_back(" << a << ", " << b << ", " << c << ", " << d << ", vector { " << op.back() - n; swp4(op.back() - 1); auto cop = op; reverse(cop.begin(), cop.end()); solutions.emplace_back(a, b, c, d, vector<int> {}); for (auto e : cop) solutions.back().ops.push_back(e - n); op.pop_back(); reverse(op.begin(), op.end()); for (auto o : op) { cout << ", " << o - n; swp4(o - 1); } cout << " });\n"; op.clear(); #endif return false; } int main() { op.reserve(1000000); bool canDo = true; solutions.emplace_back(1, 3, 4, 2, vector{ -3, -4, -3, -5, -6, -5, -6, -6, -5, -4, -5, -4, -4, -4, -6, -5, -6, -4, -5, -4, -5, -6, -4, -4, -6, -4 }); solutions.emplace_back(3, 4, 1, 2, vector{ -4, -3, -5, -4, -5, -4, -6, -5, -6, -5, -5, -5, -6, -5, -6, -4, -4, -6, -6, -6, -4, -5, -4, -4, -4, -6, -5, -4, -6, -6 }); solutions.emplace_back(2, 3, 1, 4, vector{ -5, -4, -5, -4, -6, -5, -6, -5, -6, -4, -6, -6, -4, -4, -5, -6, -5, -6, -4, -4, -6, -4, -6, -6, -6, -4, -5 }); solutions.emplace_back(3, 1, 2, 4, vector{ -5, -4, -6, -5, -6, -6, -5, -6, -6, -4, -5, -4, -6, -5, -4, -6, -6, -4, -5, -5, -4, -4, -6, -4 }); solutions.emplace_back(1, 4, 2, 3, vector{ -4, -3, -5, -4, -5, -4, -6, -5, -6, -5, -6, -4, -6, -4, -4, -4, -5, -5, -6, -5, -6, -6, -5, -5, -5, -4, -6, -4, -6 }); solutions.emplace_back(4, 1, 3, 2, vector{ -4, -3, -5, -4, -5, -4, -6, -5, -5, -3, -4, -3, -5, -6, -5, -3, -6, -4, -4, -6, -3, -3, -5, -3, -4, -6, -3, -5 }); solutions.emplace_back(2, 1, 4, 3, vector{ -4, -3, -4, -5, -4, -5, -4, -5, -5, -5, -3, -4, -5, -3, -4, -3, -6, -6, -5, -5, -4, -5, -3, -4, -3, -5 }); solutions.emplace_back(4, 2, 1, 3, vector{ -4, -3, -5, -4, -5, -4, -6, -5, -4, -5, -4, -6, -3, -5, -3, -3, -3, -5, -5, -3, -6, -3, -3, -3, -3, -3, -4, -5, -6 }); #ifndef GENANS cin >> n >> k; list.resize(n); for (int i = 0; i < n; i++) { int a; cin >> a; list[i] = a; } #else k = 4; list.resize(n); srand(time(0)); while (1) { n = 500; list.resize(n); for (int i = 0; i < n; i++) { list[i] = i + 1; } //array<int, 15> rev = { 1, 6, 8, 1, 7, 6, 7, 6, 8, 7, 8, 7, 8, 9, 8 }; //for (auto e : rev) //{ // e += n - 12; // swp4(e - 1); // op.push_back(e); //} // //return 0; // reverse l op.clear(); for (int i = 0; i < 20000; i++) { int a = rand() % (n - k + 1); swp4(a); op.push_back(a + 1); } #endif switch (k) { case 2: for (int i = 1; i <= n; i++) { auto pos = find(list.begin(), list.end(), i); int posI = pos - list.begin(); while (posI + 1 != i) { swp2(posI - 1); op.push_back(posI); pos = find(list.begin(), list.end(), i); posI = pos - list.begin(); } } break; case 3: for (int i = 1; i <= n; i++) { auto pos = find(list.begin(), list.end(), i); int posI = pos - list.begin(); if ((posI + 1) % 2 != i % 2) { canDo = false; break; } while (posI + 1 != i) { swp3(posI - 2); op.push_back(posI - 1); pos = find(list.begin(), list.end(), i); posI = pos - list.begin(); } } break; case 4: for (int i = 1; i <= n; i++) { auto pos = find(list.begin(), list.end(), i); int posI = pos - list.begin(); if (((posI + 1) % 3 + 2) % 3 == i % 3) { if ((posI + 1) - 3 > i - 1) { swp4(posI - 3); op.push_back(posI - 2); pos = find(list.begin(), list.end(), i); posI = pos - list.begin(); } if ((posI + 1) - 2 > i - 1 && posI + 1 < n) { swp4(posI - 2); op.push_back(posI - 1); } else if (posI + 3 < n) { swp4(posI - 1); op.push_back(posI); swp4(posI); op.push_back(posI + 1); } else if (posI + 4 < n) { swp4(posI); op.push_back(posI + 1); swp4(posI + 1); op.push_back(posI + 2); } else { canDo = slv(); break; } } if (((posI + 1) % 3 + 1) % 3 == i % 3) { if ((posI + 1) - 3 > i - 1) { swp4(posI - 3); op.push_back(posI - 2); pos = find(list.begin(), list.end(), i); posI = pos - list.begin(); } if ((posI + 1) - 1 > i - 1 && posI + 2 < n) { swp4(posI - 1); op.push_back(posI); } else if (posI + 5 < n) { swp4(posI); op.push_back(posI + 1); swp4(posI + 1); op.push_back(posI); swp4(posI + 2); op.push_back(posI + 3); } else { canDo = slv(); break; } } pos = find(list.begin(), list.end(), i); posI = pos - list.begin(); while (posI + 1 != i) { swp4(posI - 3); op.push_back(posI - 2); pos = find(list.begin(), list.end(), i); posI = pos - list.begin(); } } break; case 5: break; } #ifdef GENANS if (!is_sorted(list.begin(), list.end())) cout << "\n\n!!!NOT SORTED!!!\n\n"; } #endif if (op.size() > 100000) canDo = false; if (canDo) { cout << "YES\n"; cout << op.size() << "\n"; for (auto e : op) cout << e << " "; if (!is_sorted(list.begin(), list.end())) cout << "\n\n!!!NOT SORTED!!!\n\n"; } else cout << "NO\n"; return 0; }
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
5 2 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 0 |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
5 2 2 1 3 4 5 |
correct output |
---|
YES 1 1 |
user output |
---|
YES 1 1 |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
20 2 6 20 18 2 16 13 19 17 8 14 11 ... |
correct output |
---|
YES 366 2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
YES 132 19 18 17 16 15 14 13 12 11 10 ... Truncated |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
100 2 100 92 62 88 12 7 43 31 19 72 ... |
correct output |
---|
YES 2876 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 2438 77 76 75 74 73 72 71 70 69 68 ... Truncated |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
100 2 100 99 98 97 96 95 94 93 92 91... |
correct output |
---|
YES 5248 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 4950 99 98 97 96 95 94 93 92 91 90 ... Truncated |
Test 6
Group: 2
Verdict: ACCEPTED
input |
---|
5 3 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 0 |
Test 7
Group: 2
Verdict: ACCEPTED
input |
---|
5 3 3 5 4 1 2 |
correct output |
---|
NO |
user output |
---|
NO |
Test 8
Group: 2
Verdict: ACCEPTED
input |
---|
5 3 5 2 1 4 3 |
correct output |
---|
YES 8 1 2 1 3 1 2 3 1 |
user output |
---|
YES 2 1 3 |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
20 3 19 14 1 18 3 4 11 20 13 6 17 8... |
correct output |
---|
YES 52 8 10 12 14 16 18 1 3 5 7 9 11 ... |
user output |
---|
YES 42 1 12 10 8 6 4 2 3 6 4 11 9 7 5... Truncated |
Test 10
Group: 2
Verdict: ACCEPTED
input |
---|
20 3 9 6 13 18 5 10 3 2 7 20 1 4 19... |
correct output |
---|
YES 50 10 12 14 16 18 13 15 17 4 6 8 ... |
user output |
---|
YES 34 9 7 5 3 1 6 4 2 7 5 3 10 8 6 4... |
Test 11
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 53 52 21 76 25 142 5 4 83 176 ... |
correct output |
---|
YES 15194 334 336 338 340 342 344 346 34... |
user output |
---|
YES 15174 67 65 63 61 59 57 55 53 51 49 ... Truncated |
Test 12
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 51 44 147 172 1 28 27 82 233 1... |
correct output |
---|
YES 15565 366 368 370 372 374 376 378 38... |
user output |
---|
YES 15543 3 1 108 106 104 102 100 98 96 ... Truncated |
Test 13
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 75 46 179 62 221 14 67 154 89 ... |
correct output |
---|
YES 15920 454 456 458 460 462 464 466 46... |
user output |
---|
YES 15902 75 73 71 69 67 65 63 61 59 57 ... Truncated |
Test 14
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 161 54 285 12 71 142 111 94 97... |
correct output |
---|
YES 15931 408 410 412 414 416 418 420 42... |
user output |
---|
YES 15907 275 273 271 269 267 265 263 26... Truncated |
Test 15
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 122 260 455 113 315 276 433 43... |
correct output |
---|
NO |
user output |
---|
NO |
Test 16
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 499 500 497 498 495 496 493 49... |
correct output |
---|
YES 62264 2 4 6 8 10 12 14 16 18 20 22 2... |
user output |
---|
YES 62250 497 495 493 491 489 487 485 48... Truncated |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
5 4 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 0 |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
5 4 5 1 2 3 4 |
correct output |
---|
YES 4 1 2 1 2 |
user output |
---|
YES 4 1 2 1 2 |
Test 19
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 58 14 107 124 4 113 24 290 56 ... |
correct output |
---|
YES 15698 389 392 395 398 401 404 407 41... |
user output |
---|
YES 14681 24 23 22 19 16 13 10 7 4 1 19 ... Truncated |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 113 187 278 242 23 67 48 298 3... |
correct output |
---|
YES 15004 480 481 480 482 485 488 491 49... |
user output |
---|
YES 13794 265 262 259 256 253 250 247 24... Truncated |
Test 21
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 5 233 199 35 213 354 11 134 30... |
correct output |
---|
YES 16770 458 461 464 467 470 473 476 47... |
user output |
---|
YES 15407 227 225 223 220 217 214 211 20... Truncated |
Test 22
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 169 47 21 137 57 138 360 147 4... |
correct output |
---|
YES 15889 497 371 372 371 373 376 379 38... |
user output |
---|
YES 14691 58 55 52 49 46 43 40 37 34 31 ... Truncated |
Test 23
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 493 409 291 313 156 443 496 40... |
correct output |
---|
YES 22886 480 481 480 482 485 488 491 49... |
user output |
---|
YES 21757 338 336 334 331 328 325 322 31... Truncated |
Test 24
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 137 99 100 226 326 298 140 340... |
correct output |
---|
NO |
user output |
---|
NO |
Test 25
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 500 499 498 497 496 495 494 49... |
correct output |
---|
YES 41458 1 2 1 2 5 8 11 14 17 20 23 26 ... |
user output |
---|
YES 41421 497 495 493 490 487 484 481 47... Truncated |
Test 26
Group: 4
Verdict: ACCEPTED
input |
---|
5 5 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 0 |
Test 27
Group: 4
Verdict: WRONG ANSWER
input |
---|
5 5 5 4 3 2 1 |
correct output |
---|
YES 1 1 |
user output |
---|
YES 0 !!!NOT SORTED!!! ... |
Test 28
Group: 4
Verdict: WRONG ANSWER
input |
---|
500 5 145 26 285 154 147 314 141 40 ... |
correct output |
---|
YES 13786 216 220 224 228 232 236 240 24... |
user output |
---|
YES 0 !!!NOT SORTED!!! ... |
Test 29
Group: 4
Verdict: WRONG ANSWER
input |
---|
500 5 137 22 399 292 249 6 51 224 42... |
correct output |
---|
YES 13465 456 460 464 468 472 476 480 48... |
user output |
---|
YES 0 !!!NOT SORTED!!! ... |
Test 30
Group: 4
Verdict: WRONG ANSWER
input |
---|
500 5 153 52 85 100 329 60 433 468 4... |
correct output |
---|
YES 13642 377 378 377 380 384 388 392 39... |
user output |
---|
YES 0 !!!NOT SORTED!!! ... |
Test 31
Group: 4
Verdict: WRONG ANSWER
input |
---|
500 5 267 326 95 108 189 32 291 366 ... |
correct output |
---|
YES 14639 213 214 213 216 220 224 228 23... |
user output |
---|
YES 0 !!!NOT SORTED!!! ... |
Test 32
Group: 4
Verdict: WRONG ANSWER
input |
---|
500 5 15 450 272 80 321 101 247 438 ... |
correct output |
---|
NO |
user output |
---|
YES 0 !!!NOT SORTED!!! ... |
Test 33
Group: 4
Verdict: WRONG ANSWER
input |
---|
499 5 497 498 499 496 495 494 493 49... |
correct output |
---|
YES 30886 3 7 11 15 19 23 27 31 35 39 43... |
user output |
---|
YES 0 !!!NOT SORTED!!! ... |
Test 34
Group: 4
Verdict: WRONG ANSWER
input |
---|
500 5 499 500 497 498 495 496 493 49... |
correct output |
---|
YES 30919 1 4 8 12 16 20 24 28 32 36 40 ... |
user output |
---|
YES 0 !!!NOT SORTED!!! ... |