Task: | Käännöt |
Sender: | perusjuntti |
Submission time: | 2023-11-11 22:49:54 +0200 |
Language: | C++ (C++11) |
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.01 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 <bits/stdc++.h>using namespace std;bool sorted = 0;set<vector<int>> st;vector<int> ops_5, ops_6, ops_7, ops_other;void k2(int n, vector<int> a) {vector<int> ans;for (int i = 1; i <= n; ++i) for (int j = 0; j < n; ++j) if (a[j] == i) for (int k = j+1; k > i; --k) {swap(a[k-1],a[k-2]);ans.push_back(k-1);}cout << "YES\n" << ans.size() << '\n';for (int &i:ans) cout << i << ' ';}void k3(int n, vector<int> a) {for (int i = 0; i < n; ++i) if ((a[i] & 1) != ((i+1) & 1)) {cout << "NO\n";return;}vector<int> ans;for (int i = 1; i <= n; ++i) for (int j = 0; j < n; ++j) if (a[j] == i) for (int k = j; k > i; --k) {swap(a[k],a[k-2]);ans.push_back(k-1);}cout << "YES\n" << ans.size() << '\n';for (int &i:ans) cout << i << ' ';}//k == 4void sort_other(vector<int> &a, int n) {for (int i = 1; i <= n-6; ++i) {for (int j = 0; j < n; ++j) {if (a[j] == i) {if (j == i-1)break;//oikeassa paikassa melkeinif (j % 3 == (i-1) % 3) {for (int k = j-3; k >= i-1; k -= 3) {swap(a[k],a[k+3]);swap(a[k+1],a[k+2]);ops_other.push_back(k+1);}}//pitää shiftata yhdellä taaksepäinelse if (j % 3 == i % 3) {if (j < n-4) {swap(a[j],a[j+3]);swap(a[j+1],a[j+2]);ops_other.push_back(j+1);j += 3;swap(a[j-2],a[j+1]);swap(a[j-1],a[j]);ops_other.push_back(j-1);--j;}else {swap(a[j-3],a[j]);swap(a[j-2],a[j-1]);ops_other.push_back(j-2);j -= 3;swap(a[j-1],a[j+2]);swap(a[j],a[j+1]);ops_other.push_back(j);++j;swap(a[j-1],a[j+2]);swap(a[j],a[j+1]);ops_other.push_back(j);++j;}for (int k = j-3; k >= i-1; k -= 3) {swap(a[k],a[k+3]);swap(a[k+1],a[k+2]);ops_other.push_back(k+1);}}//pitää siirtää yhdellä eteenpäinelse {if (j < n-2 && j >= 1) {swap(a[j-1],a[j+2]);swap(a[j],a[j+1]);ops_other.push_back(j);++j;}else if (j == 0) {swap(a[0],a[3]);swap(a[1],a[2]);ops_other.push_back(1);swap(a[2],a[5]);swap(a[3],a[4]);ops_other.push_back(3);j = 4;}else {swap(a[j-3],a[j]);swap(a[j-2],a[j-1]);ops_other.push_back(j-2);j -= 3;swap(a[j-1],a[j+2]);swap(a[j],a[j+1]);ops_other.push_back(j);++j;}for (int k = j-3; k >= i-1; k -= 3) {swap(a[k],a[k+3]);swap(a[k+1],a[k+2]);ops_other.push_back(k+1);}}}}}}void sort_6(vector<int> a, vector<int> ops) {if (sorted)return;if (st.count(a))return;st.insert(a);bool ok = 1;for (int i = 0; i < 6; ++i)if (a[i] != i+1)ok = 0;if (ok) {sorted = 1;for (int &i:ops)ops_6.push_back(i);return;}else {swap(a[0],a[3]);swap(a[1],a[2]);ops.push_back(1);sort_6(a,ops);ops.pop_back();swap(a[0],a[3]);swap(a[1],a[2]);swap(a[1],a[4]);swap(a[2],a[3]);ops.push_back(2);sort_6(a,ops);ops.pop_back();swap(a[1],a[4]);swap(a[2],a[3]);swap(a[2],a[5]);swap(a[3],a[4]);ops.push_back(3);sort_6(a,ops);}}bool sort_5(vector<int> a) {bool ok = 1;for (int i = 0; i < 5; ++i) {if (a[i] != i+1)ok = 0;}if (ok)return ok;for (int i = 1; i <= 10; ++i) {if (i & 1) {swap(a[0],a[3]);swap(a[1],a[2]);ops_5.push_back(1);}else {swap(a[1],a[4]);swap(a[2],a[3]);ops_5.push_back(2);}ok = 1;for (int i = 0; i < 5; ++i) {if (a[i] != i+1)ok = 0;}if (ok)break;}return ok;}void k_4(int n, vector<int> a) {vector<int> ops, rest;if (n == 5) {if (sort_5(a)) {cout << "YES\n";cout << ops_5.size() << '\n';for (int &i:ops_5)cout << i << ' ';}elsecout << "NO\n";return;}sort_other(a,n);bool skip = 1;for (int i = 0; i < n; ++i)if (a[i] != i+1)skip = 0;for (int i = n-6; i < n; ++i) {rest.push_back(a[i]-(n-6));}sort_6(rest,ops);if (ops_6.size() || skip) {cout << "YES\n";cout << ops_6.size() + ops_other.size() << '\n';for (int &i:ops_other)cout << i << ' ';for (int &i:ops_6)cout << i+n-6 << ' ';}elsecout << "NO\n";}//k == 5void sort_other_k5(vector<int> &a, int n) {for (int i = 1; i <= n-7; ++i) {for (int j = 0; j < n; ++j) {if (a[j] == i) {if (j == i-1)break;if (i % 4 == (j+1) % 4) {for (int k = j-4; k >= i-1; k -= 4) {swap(a[k],a[k+4]);swap(a[k+1],a[k+3]);ops_other.push_back(k+1);}}else {if (j < n-3) {swap(a[j-1],a[j+3]);swap(a[j],a[j+2]);ops_other.push_back(j);j += 2;}else {swap(a[j-4],a[j]);swap(a[j-3],a[j-1]);ops_other.push_back(j-3);j -= 4;swap(a[j-1],a[j+3]);swap(a[j],a[j+2]);ops_other.push_back(j);j += 2;}for (int k = j-4; k >= i-1; k -= 4) {swap(a[k],a[k+4]);swap(a[k+1],a[k+3]);ops_other.push_back(k+1);}}}}}}bool sort_6_k5(vector<int> a) {bool ok = 1;for (int i = 0; i < 6; ++i) {if (a[i] != i+1)ok = 0;}if (ok)return ok;for (int i = 1; i <= 20; ++i) {if (i & 1) {swap(a[0],a[4]);swap(a[1],a[3]);ops_6.push_back(1);}else {swap(a[1],a[5]);swap(a[2],a[4]);ops_6.push_back(2);}ok = 1;for (int i = 0; i < 6; ++i) {if (a[i] != i+1)ok = 0;}if (ok)break;}return ok;}void sort_7_k5(vector<int> a, vector<int> ops) {if (sorted)return;if (st.count(a))return;st.insert(a);bool ok = 1;for (int i = 0; i < 7; ++i)if (a[i] != i+1)ok = 0;if (ok) {sorted = 1;for (int &i:ops)ops_7.push_back(i);return;}else {swap(a[0],a[4]);swap(a[1],a[3]);ops.push_back(1);sort_7_k5(a,ops);ops.pop_back();swap(a[0],a[4]);swap(a[1],a[3]);swap(a[1],a[5]);swap(a[2],a[4]);ops.push_back(2);sort_7_k5(a,ops);ops.pop_back();swap(a[1],a[5]);swap(a[2],a[4]);swap(a[2],a[6]);swap(a[3],a[5]);ops.push_back(3);sort_7_k5(a,ops);}}void k_5(int n, vector<int> a) {vector<int> ops, rest;bool good = 1;for (int i = 0; i < n; ++i) {if ((a[i] & 1) != ((i+1) & 1))good = 0;}if (!good) {cout << "NO\n";return;}if (n == 5) {vector<int> s = {1,2,3,4,5}, r = {5,4,3,2,1};if (a == s)cout << "YES\n0";else if (a == r)cout << "YES\n1\n1";elsecout << "NO\n";return;}if (n == 6) {if (sort_6_k5(a)) {cout << "YES\n";cout << ops_6.size() << '\n';for (int &i:ops_6)cout << i << ' ';}elsecout << "NO\n";return;}sort_other_k5(a,n);bool skip = 1;for (int i = 0; i < n; ++i)if (a[i] != i+1)skip = 0;for (int i = n-7; i < n; ++i) {rest.push_back(a[i]-(n-7));}sort_7_k5(rest,ops);if (ops_7.size() || skip) {cout << "YES\n";cout << ops_7.size() + ops_other.size() << '\n';for (int &i:ops_other)cout << i << ' ';//cout << '\n';for (int &i:ops_7)cout << i+n-7 << ' ';//cout << '\n';}elsecout << "NO\n";}int main() {int n, k;cin >> n >> k;vector<int> ops, a(n);for (int &i:a) cin >> i;if (k == 2) {k2(n,a);return 0;}else if (k == 3) {k3(n,a);return 0;}else if (k == 4) {k_4(n,a);return 0;}else if (k == 5) {k_5(n,a);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 68 1 12 11 10 9 8 7 6 5 4 3 2 5 4... 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 54 9 8 7 6 5 4 3 2 1 8 7 6 5 4 3 ... Truncated |
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 34072 67 66 65 64 63 62 61 60 59 58 ... 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 35099 3 2 1 108 107 106 105 104 103 ... 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 33488 75 74 73 72 71 70 69 68 67 66 ... 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 35497 275 274 273 272 271 270 269 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 496 495 494 493 492 491 49... 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 15065 26 25 22 19 16 13 10 7 4 1 21 ... 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 14165 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 15923 230 231 229 226 223 220 217 21... 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 15043 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 22264 341 342 340 337 334 331 328 32... 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 41566 497 496 497 496 493 490 487 48... 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 13248 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 13189 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 13136 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 14119 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 30886 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 31407 495 494 493 489 485 481 477 47... Truncated |