Task: | Käännöt |
Sender: | stpn129 |
Submission time: | 2023-11-09 11:46:41 +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.00 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.01 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;void init_code() {ios_base::sync_with_stdio(0);cin.tie(0);#ifndef ONLINE_JUDGEfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);#endif}bool is_ok(int j, int i, int n, int k) {if (j < 1 || (j + (k - 1)) > n || j < i) {return false;}return true;}void rev(int i, int k, vector<int>& a, vector<int>& pos, vector<int>& res) {reverse(a.begin() + i, a.begin() + i + k);for (int ik = 0; ik <= k - 1; ++ik) {pos[a[i + ik]] = i + ik;}res.push_back(i);}vector<int> compress(vector<int>& a) {vector<int> b = a;sort(b.begin(), b.end());b.erase(unique(b.begin(), b.end()), b.end());for (int &x : a)x = int(lower_bound(b.begin(), b.end(), x) - b.begin()) + 1;return a;}vector<int> solve2(int n, int k, vector<int>& a) {queue<vector<int>> q;q.push(a);map<vector<int>, int> d;d[a] = 0;map<vector<int>, vector<int>> prev;map<vector<int>, int> prev_op;prev_op[a] = -1;while (!q.empty()) {vector<int> v = q.front();q.pop();if (is_sorted(v.begin(), v.end())) {vector<int> ops;while (prev_op[v] != -1) {ops.push_back(prev_op[v] + 1);v = prev[v];}reverse(ops.begin(), ops.end());return ops;}for (int i = 0; i < n - (k - 1); ++i) {vector<int> next = v;reverse(next.begin() + i, next.begin() + i + k);if (!d.count(next) || d[next] > d[v] + 1) {q.push(next);prev[next] = v;prev_op[next] = i;d[next] = d[v] + 1;}}}return vector<int> ();}void solve() {int n, k;cin >> n >> k;vector<int> a(n + 1, -1), pos(n + 1);for (int i = 1; i <= n; ++i) {cin >> a[i];pos[a[i]] = i;}vector<int> res;if (n <= 8) {a.erase(a.begin());res = solve2(n, k, a);if (res.size() > 0 || is_sorted(a.begin(), a.end())) {cout << "YES" << '\n';cout << res.size() << '\n';for (auto i : res) {cout << i << ' ';}cout << '\n';} else {cout << "NO" << '\n';}return;}for (int i = 1; i <= n; ++i) {if (a[i] == i) {continue;}int j = pos[i];vector<int> fix;if ((j - i) % (k - 1) != 0) {queue<pair<vector<int>, int>> q;q.push({vector<int> (), j});int x = 0;while (!q.empty() && x <= 100) {vector<int> op = q.front().first;int cur_j = q.front().second;q.pop();if (cur_j < i) {continue;}if ((cur_j - i) % (k - 1) == 0) {fix = op;break;}for (int it = cur_j - (k - 1); it <= cur_j; ++it) {if (is_ok(it, i, n, k)) {op.push_back(it);int new_j = it + k - (abs(cur_j - it) + 1);q.push({op, new_j});op.pop_back();x++;}}}}for (auto it : fix) {rev(it, k, a, pos, res);}j = pos[i];if ((j - i) % (k - 1) == 0) {while (j != i) {rev(j - (k - 1), k, a, pos, res);j -= (k - 1);}} else {break;}}if (is_sorted(a.begin() + 1, a.end())) {cout << "YES" << '\n';cout << res.size() << '\n';for (auto i : res) {cout << i << ' ';}cout << '\n';return;}vector<int> lst;for (int i = n - 8; i <= n; ++i) {lst.push_back(a[i]);}lst = compress(lst);if (k == 4) {map<vector<int>, vector<int>> mp;mp[{1, 2, 3, 4, 5, 6, 8, 9, 7}] = {4, 3, 6, 3, 5, 6, 3, 5};mp[{1, 2, 3, 4, 5, 6, 9, 7, 8}] = {5, 3, 6, 5, 3, 6, 3, 4};mp[{1, 2, 3, 4, 5, 7, 6, 9, 8}] = {4, 5, 4, 6, 4, 5, 4};mp[{1, 2, 3, 4, 5, 7, 8, 6, 9}] = {3, 2, 5, 2, 4, 5, 2, 4};mp[{1, 2, 3, 4, 5, 7, 9, 8, 6}] = {3, 2, 5, 6, 5, 4, 2, 3};mp[{1, 2, 3, 4, 5, 8, 6, 7, 9}] = {4, 2, 5, 4, 2, 5, 2, 3};mp[{1, 2, 3, 4, 5, 8, 7, 9, 6}] = {4, 5, 4, 3, 6, 3, 6, 3};mp[{1, 2, 3, 4, 5, 8, 9, 6, 7}] = {4, 3, 4, 6, 4, 3, 4};mp[{1, 2, 3, 4, 5, 9, 6, 8, 7}] = {3, 2, 4, 5, 6, 5, 2, 3};mp[{1, 2, 3, 4, 5, 9, 7, 6, 8}] = {3, 5, 3, 6, 5, 4, 3, 5};mp[{1, 2, 3, 4, 5, 9, 8, 7, 6}] = {6};for (auto i : mp[lst]) {rev(i + (n - 9), k, a, pos, res);}} else if (k == 5) {vector<int> tmp = solve2(9, k, lst);for (auto i : tmp) {rev(i + (n - 9), k, a, pos, res);}}if (is_sorted(a.begin() + 1, a.end())) {cout << "YES" << '\n';cout << res.size() << '\n';for (auto i : res) {cout << i << ' ';}cout << '\n';return;}cout << "NO" << '\n';}signed main() {init_code();int t = 1;// cin >> t;while (t--) {solve();}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... 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 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 14534 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 13736 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 15521 228 226 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 14658 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 21770 339 337 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 41416 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 13116 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 12895 468 465 461 457 453 449 445 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 12910 204 201 197 193 189 185 181 17... 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 13851 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 30630 495 492 489 485 481 477 473 46... 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 30881 496 493 489 485 481 477 473 46... Truncated |