Task: | Käännöt |
Sender: | qanpi |
Submission time: | 2023-11-11 16:08:21 +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.36 s | 3 | details |
#20 | ACCEPTED | 0.36 s | 3 | details |
#21 | ACCEPTED | 0.36 s | 3 | details |
#22 | ACCEPTED | 0.01 s | 3 | details |
#23 | ACCEPTED | 0.01 s | 3 | details |
#24 | ACCEPTED | 0.00 s | 3 | details |
#25 | ACCEPTED | 0.36 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<bits/stdc++.h>#include <queue>#include<unordered_set>#include<vector>#include<chrono>using namespace std;typedef long long ll;constexpr ll M = 1000000007;constexpr ll P = (1 << 18);constexpr int INF = 1e9;int arr[510] = {0};int ops[1000001];int n, k;int steps = 0;string target;void solve() {bool ordered = false;//do while?while (!ordered) {ordered = true;for (int i=1; i<n; i++) {switch (k) {case 2:if (arr[i] > arr[i+1]) {ordered = false;swap(arr[i], arr[i+1]);ops[steps++] = i;}break;case 3:if (i+2 <= n && (arr[i] > arr[i+2] || arr[i] > arr[i+1])) {ordered = false;swap(arr[i], arr[i+2]);ops[steps++] = i;}break;case 4:if (i+3 <= n) {if (i == ops[steps-1]) continue;int delta = 0;if (arr[i] > arr[i+3]) {ordered = false;delta++;} else delta--;if (arr[i+1] > arr[i+2]) {ordered = false;delta++;} else delta--;if (arr[i] < arr[i+1]) delta--;else delta++;if (arr[i+2] < arr[i+3]) delta--;else delta++;if (delta < 0) {for (int j=1; j<=n; j++) {cout << arr[j] << " ";}cout << endl;continue;};swap(arr[i], arr[i+3]);swap(arr[i+1], arr[i+2]);ops[steps++] = i;cout << steps << ": " << i << endl;}}}}}int compute_score(int i) {int score = 0; //higher = betterint breakpoints = 0;if (abs(arr[i+k] - arr[i]) == 1) breakpoints--;if (abs(arr[i-1] - arr[i+k-1]) == 1) breakpoints--;score -= breakpoints;int inversions = 0;if (k==4) {if (arr[i] > arr[i+1]) inversions--;if (arr[i] > arr[i+2]) inversions--;if (arr[i] > arr[i+3]) inversions--;if (arr[i+1] > arr[i+2]) inversions--;if (arr[i+1] > arr[i+3]) inversions--;if (arr[i+2] > arr[i+3]) inversions--;} else if (k==5) {if(arr[i] > arr[i+1]) inversions--;if(arr[i] > arr[i+2]) inversions--;if(arr[i] > arr[i+3]) inversions--;if(arr[i] > arr[i+4]) inversions--;if (arr[i+1] > arr[i+2]) inversions--;if (arr[i+1] > arr[i+3]) inversions--;if (arr[i+1] > arr[i+4]) inversions--;if (arr[i+2] > arr[i+3]) inversions--;if (arr[i+2] > arr[i+4]) inversions--;if (arr[i+3] > arr[i+4]) inversions--;}score -= inversions;//int distance = arr[i] - i;//score += floor(distance / 4);return score;}unordered_set<string> seen;int seen_count = 0;void reverse(int a) {ops[steps++] = a;if (k == 4) {swap(arr[a], arr[a+3]);swap(arr[a+1], arr[a+2]);} else if (k == 5) {swap(arr[a], arr[a+4]);swap(arr[a+1], arr[a+3]);}//cout << a << ": ";//for (int i=1; i<=n; i++) {// cout << arr[i] << " ";//}//cout << endl;}bool search() {if (steps > 1000000) {return false;}priority_queue<pair<int, int>> q;string hashed = "";bool ordered = true;for (int i=1; i<n; i++) {hashed += to_string(arr[i]) + " ";if (arr[i] > arr[i+1]) ordered = false;if (i <= n-k+1) {int score = compute_score(i);q.push({score, i});}}if (ordered) return true;//cout << hashed << endl;if (seen.count(hashed)) return false;seen.insert(hashed);while (!q.empty()) {int a = q.top().second; q.pop();if (a == ops[steps-1]) continue;reverse(a);bool b = search();if (b) return true;reverse(a);steps-=2;}return false;}void prime() {if (k == 4) {for (int i=n; i>=5; i--) {for (int j=1; j<=n; j++) {if (i == arr[j]) {int pos = j;int distance = arr[pos] - pos;while (distance >= 3) {reverse(pos);pos = pos + 3;distance = arr[pos] - pos;}switch (distance % 3) {case 1:reverse(pos-2);pos = pos - 1;reverse(pos-2);pos = pos - 1;reverse(pos);pos = pos + 3;break;case 2:reverse(pos-2);pos = pos - 1;reverse(pos);pos = pos + 3;}}}}} else if (k == 5) {for (int i=n; i>=6; i--) {for (int j=1; j<=n; j++) {if (i == arr[j]) {int pos = j;int distance = arr[pos] - pos;while (distance >= 4) {reverse(pos);pos = pos + 4;distance = arr[pos] - pos;}switch (distance % 4) {case 2:reverse(pos-3);pos = pos - 2;reverse(pos);pos = pos + 4;break;}}}}}}int main() {cin >> n >> k;for (int i=1; i<=n; i++) {cin >> arr[i];int distance = abs(arr[i] - i);switch (k) {case 3:case 5:if (distance % 2 == 1) {cout << "NO" << endl;return 0;} break;}}int inversions = 0;int strips = 0;arr[0] = -1;for (int i=1; i<=n; i++) {if (abs(arr[i] - arr[i-1]) != 1) strips++;//int prev = inversions;for (int j=i+1; j<=n; j++) {if (arr[i] > arr[j]) inversions++;}//cout << inversions - prev << " ";}//cout << strips << endl;//cout << endl;if (k == 4 && (inversions % 2 == 1 || (n == 5 && strips > 2))) {cout << "NO" << endl;return 0;}if (k == 5 && (inversions % 2 == 1 || (n == 5 && strips > 1) || (n == 6 && strips > 2))) {cout << "NO" << endl;return 0;}//cout << inversions << endl;if (k==2||k==3) solve();else {prime();search();}cout << "YES" << endl;cout << steps << endl;for (int i=0; i<steps; i++) {cout << ops[i] << " ";}cout << endl;//for (int i=1; i<=n; i++) {// cout << arr[i] << " ";//}//cout << endl;}
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 2 3 4 5 6 7 8 9 10 11 12 13 14... 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 1 2 3 4 5 6 7 8 9 10 11 12 13 ... 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 1 2 3 4 5 6 7 8 9 10 11 12 13 ... 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 58 1 3 4 5 7 8 9 10 11 12 13 14 1... 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 44 1 3 4 5 6 7 8 9 10 12 13 14 15... 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 26114 1 3 4 5 6 10 11 12 13 14 15 16... 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 27011 1 3 4 5 6 8 9 10 11 12 13 15 1... 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 26438 1 3 4 5 8 9 10 12 13 14 15 16 ... 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 27533 1 2 3 5 6 7 8 9 10 11 13 14 15... 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 1 2 3 4 5 6 7 8 9 10 11 12 13 ... 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 23916 389 392 395 398 401 404 407 41... 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 23077 484 487 490 493 496 497 496 49... 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 24840 458 461 464 467 470 473 476 47... 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 14991 497 375 378 381 384 387 390 39... 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 21898 484 487 490 493 496 497 496 49... 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 51262 1 4 7 10 13 16 19 22 25 28 31 ... 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 13310 216 220 224 228 232 236 240 24... 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 12973 456 460 464 468 472 476 480 48... 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 382 386 390 394 398 402 406 41... 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 14145 218 222 226 230 234 238 242 24... 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 3 7 11 15 19 23 27 31 35 39 43... 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 31509 2 6 10 14 18 22 26 30 34 38 42... Truncated |