Task: | Käännöt |
Sender: | cppbetter |
Submission time: | 2023-11-01 19:17:36 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 13 |
#2 | ACCEPTED | 19 |
#3 | ACCEPTED | 33 |
#4 | ACCEPTED | 35 |
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 | ACCEPTED | 0.00 s | 4 | details |
#28 | ACCEPTED | 0.01 s | 4 | details |
#29 | ACCEPTED | 0.01 s | 4 | details |
#30 | ACCEPTED | 0.01 s | 4 | details |
#31 | ACCEPTED | 0.01 s | 4 | details |
#32 | ACCEPTED | 0.00 s | 4 | details |
#33 | ACCEPTED | 0.01 s | 4 | details |
#34 | ACCEPTED | 0.01 s | 4 | details |
Code
#include <iostream>#include <vector>#include <array>#include <algorithm>//#define GENANSusing 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 Solution4{int a, b, c, d;vector<int> ops;};vector<Solution4> solutions4;bool slv4(){// Get last 4 numbsint 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 : solutions4){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 solutioncout << "solutions4.emplace_back(" << a << ", " << b << ", " << c << ", " << d << ", vector { " << op.back() - n;swp4(op.back() - 1);auto cop = op;reverse(cop.begin(), cop.end());solutions4.emplace_back(a, b, c, d, vector<int> {});for (auto e : cop)solutions4.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();#endifreturn false;}struct Solution5{int a, b, c, d, e;vector<int> ops;};vector<Solution5> solutions5;bool slv5(){// Get last 4 numbsint a, b, c, d, e;a = list[n - 5] - n + 4;b = list[n - 4] - n + 4;c = list[n - 3] - n + 4;d = list[n - 2] - n + 4;e = list[n - 1] - n + 4;for (auto s : solutions5){if (s.a == a && s.b == b && s.c == c && s.d == d && s.e == e){for (auto o : s.ops){op.push_back(o + n);swp5(o - 1 + n);}return true;}}#ifdef GENANS// reverse of the operetions is the solutioncout << "solutions5.emplace_back(" << a << ", " << b << ", " << c << ", " << d << ", " << e << ", vector { " << op.back() - n;swp5(op.back() - 1);auto cop = op;reverse(cop.begin(), cop.end());solutions5.emplace_back(a, b, c, d, e, vector<int> {});for (auto e : cop)solutions5.back().ops.push_back(e - n);op.pop_back();reverse(op.begin(), op.end());for (auto o : op){cout << ", " << o - n;swp5(o - 1);}cout << " });\n";op.clear();#endifreturn false;}int main(){op.reserve(1000000);bool canDo = true;solutions4.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 });solutions4.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 });solutions4.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 });solutions4.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 });solutions4.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 });solutions4.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 });solutions4.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 });solutions4.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 });solutions5.emplace_back(2, 3, 0, 1, 4, vector{ -6, -5, -5, -5, -4, -4, -6, -4, -4, -4, -4, -5, -4, -6, -6, -4, -4, -6, -4, -6, -6 });solutions5.emplace_back(0, 3, 4, 1, 2, vector{ -4, -6, -5, -6, -5, -6, -5, -5, -5, -5, -6, -4, -6, -6, -6, -5, -4, -6, -6, -4, -5, -4, -4 });solutions5.emplace_back(4, 1, 0, 3, 2, vector{ -5, -6, -5, -4, -6, -4, -5, -4, -6, -5, -4, -6, -4, -6, -5, -5, -5, -6, -6, -5, -6, -4, -4, -6 });#ifndef GENANScin >> n >> k;list.resize(n);for (int i = 0; i < n; i++){int a;cin >> a;list[i] = a;}#elsek = 5;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 lop.clear();for (int i = 0; i < 50000; i++){int a = rand() % (n - k + 1);swp5(a);op.push_back(a + 1);}#endifswitch (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 = slv4();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 = slv4();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: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;}if ((posI + 1) % 4 != i % 4){if ((posI + 1) + 2 < n){swp5(posI - 1);op.push_back(posI);}else if ((posI + 1) - 3 > i - 1 && (posI + 1) + 1 < n){swp5(posI - 3);op.push_back(posI - 2);}else if ((posI + 1) - 5 > i - 1){swp5(posI - 4);op.push_back(posI - 3);swp5(posI - 4 - 1);op.push_back(posI - 3 - 1);}else{canDo = slv5();break;}}pos = find(list.begin(), list.end(), i);posI = pos - list.begin();while (posI + 1 != i){swp5(posI - 4);op.push_back(posI - 3);pos = find(list.begin(), list.end(), i);posI = pos - list.begin();}}break;}#ifdef GENANSif (!is_sorted(list.begin(), list.end()))cout << "\n\n!!!NOT SORTED!!!\n\n";}#endifif (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";}elsecout << "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: ACCEPTED
input |
---|
5 5 5 4 3 2 1 |
correct output |
---|
YES 1 1 |
user output |
---|
YES 1 1 |
Test 28
Group: 4
Verdict: ACCEPTED
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 13204 81 77 73 69 65 61 57 53 49 45 ... Truncated |
Test 29
Group: 4
Verdict: ACCEPTED
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 13151 470 469 465 461 457 453 449 44... Truncated |
Test 30
Group: 4
Verdict: ACCEPTED
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 13122 206 205 201 197 193 189 185 18... Truncated |
Test 31
Group: 4
Verdict: ACCEPTED
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 14097 361 357 353 349 345 341 337 33... Truncated |
Test 32
Group: 4
Verdict: ACCEPTED
input |
---|
500 5 15 450 272 80 321 101 247 438 ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 33
Group: 4
Verdict: ACCEPTED
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 30876 495 494 493 489 485 481 477 47... Truncated |
Test 34
Group: 4
Verdict: ACCEPTED
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 31395 495 494 493 489 485 481 477 47... Truncated |