Task: | Käännöt |
Sender: | Username* |
Submission time: | 2023-11-11 13:45:18 +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.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.00 s | 4 | details |
#33 | ACCEPTED | 0.01 s | 4 | details |
#34 | ACCEPTED | 0.01 s | 4 | details |
Compiler report
input/code.cpp: In function 'int inversions(std::vector<int>)': input/code.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 11 | for (int i = 0; i < vec.size(); ++i) { | ~~^~~~~~~~~~~~ input/code.cpp:12:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 12 | for (int j = i+1; j < vec.size(); ++j) { | ~~^~~~~~~~~~~~ input/code.cpp: In function 'bool parity(std::vector<int>)': input/code.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 23 | for (int i = 0; i < vec.size(); ++i) { | ~~^~~~~~~~~~~~
Code
#include <vector>#include <algorithm>#include <iostream>#include <queue>#include <map>using namespace std;int inversions(vector<int> vec) { //check inversions for k=4int inversions = 0;for (int i = 0; i < vec.size(); ++i) {for (int j = i+1; j < vec.size(); ++j) {if (vec[j] < vec[i]) {++inversions;}}}//cout << "INV: " << inversions << endl;return inversions;}bool parity(vector<int> vec) {for (int i = 0; i < vec.size(); ++i) {if ((vec[i] & 1) != ((i + 1) & 1)) { // if a value and its index have mismatching parity, applicable for k=3, k=5return false;}}return true;}vector<int> bfs(vector<int> vec, int k) {vector<int> steps = {};int n = vec.size();vector<int> sorted = vec;sort(sorted.begin(), sorted.end());map<vector<int>, int> dist; // map of lists and their distances to startmap<vector<int>, int> parent; // map of lists and the previous operation used to reach itqueue<vector<int>> q; // bfs queuedist[vec] = 0; // the intial list is distance 0q.push(vec); // start with the initial listwhile (!q.empty()) { // checks all possibilities until it finds a solutionvector<int> cur = q.front(); // checking the first value of queueq.pop();if (cur == sorted) { //end if sorted was foundbreak;}for (int i = 0; i <= n - k; i++) { // for all possible reversalsvector<int> next = cur;reverse(next.begin() + i, next.begin() + i + k);if (!dist.count(next)) { // if not already founddist[next] = dist[cur] + 1;parent[next] = i + 1;q.push(next); // add substates to queue to check}}}if (dist.count(sorted)) {for (vector<int> v = sorted; v != vec; v = v) {steps.push_back(parent[v]);reverse(v.begin() + parent[v] - 1, v.begin() + parent[v] - 1 + k);}reverse(steps.begin(), steps.end()); //reverse steps because they were traced back}return steps;}vector<int> solve(int n, int k, vector<int> vec) {vector<int> steps = {};int invs = inversions(vec);if (k == 3 || k == 5) {if (!parity(vec)) {//cout << "\nParity : unsolvable\n";return steps;}}if (k == 4) {if (invs & 1) { // number of inversions is odd : unsolvable with k=4//cout << "\nInversion parity with k=4 : unsolvable\n";return steps;}if (n <= 6) {//cout << "\nDoing bfs, short list w/ k=4\n";return bfs(vec, k);}}vector<int> moveset;bool run = true;int ceil = n-1; // ceiling based on sorted valuesint cur = n; // current value to sortint curi = -1; // current index of the value to sortwhile (run) {for (int i = ceil; i >= 0; --i) { // find largest unsorted valueif (vec[i] == cur) {if (vec[i] == i + 1) {--ceil;--cur;//cout << "\nSkip: " << cur;if (ceil < k + 2 && k>3) {//cout << "\nCEIL: " << ceil;run = false;break;}continue;}curi = i;//cout << "\nCur: " << cur << " & Cur i: " << curi;break; // found}}if (run == false) {break;}// sort the found value to its spotint targeti = cur - k; ////cout << "\nTarget: " << targeti;while (curi != targeti) {int dist = targeti - curi;bool right = dist > 0;dist = abs(dist);//cout << "\nDistance: " << dist;//cout << "\nk-1: " << k-1;if (k - 1 <= dist) {steps.push_back(curi+1);reverse(vec.begin() + curi, vec.begin() + curi + k);curi += (k - 1);//cout << "\ncuri now " << curi;/*cout << "\n";for (int i : vec) {cout << " " << i;}*/}else { // closer than k to targetif (curi == 0) { // at the leftmost side, value has to be moved out firststeps.push_back(curi+1);reverse(vec.begin() + curi, vec.begin() + curi + k);curi += (k - 1);/*cout << "\n";for (int i : vec) {cout << " " << i;}*/continue;}//cout << "\nclose to tgt";if (k == 4) {if (right) {for (int i = 0; i < dist; ++i) {steps.push_back(curi);reverse(vec.begin() + curi - 1, vec.begin() + curi + k-1);++curi;}//cout << "\ngoing tgt";}else { // edge case where value has ended up past the targetfor (int i = 0; i < dist; ++i) {steps.push_back(curi-1);reverse(vec.begin() + curi - 2, vec.begin() + curi + k - 2);--curi;}//cout << "\npast tgt";}}else if (k == 5) {if (right) {steps.push_back(curi);reverse(vec.begin() + curi - 1, vec.begin() + curi + k - 1);curi += 2;//cout << "\ngoing tgt";}else { // edge case where value has ended up past the targetsteps.push_back(curi - 2);reverse(vec.begin() + curi - 3, vec.begin() + curi + k - 3);curi -= 2;//cout << "\npast tgt";}}break;}}//cout << "\nREACHED TARGET";/*cout << "\n";for (int i : vec) {cout << " " << i;}*/steps.push_back(curi + 1);reverse(vec.begin() + curi, vec.begin() + curi + k);//cout << "\nDONE";/*cout << "\n";for (int i : vec) {cout << " " << i;}*/if (is_sorted(vec.begin(), vec.end())) {break;}}/*cout << "\nFINAL LIST :: \n";cout << "\n";for (int i : vec) {cout << " " << i;}*/if (!is_sorted(vec.begin(), vec.end())) {if (k > 3) { // find solution to unsorted part using bfsvector<int> subvec(vec.begin(), vec.begin() + k + 2);vector<int> substeps = bfs(subvec, k);if (substeps.size() > 0) {steps.insert(steps.end(), substeps.begin(), substeps.end());}else {steps = {};}}}//cout << "\n";return steps;}int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);// take inputsint n, k;cin >> n;cin >> k;vector<int> vec(n);for (int i = 0; i < n; i++) {cin >> vec[i];}// end of inputsif (is_sorted(vec.begin(), vec.end())) { //already sorted, return YES 0cout << "YES\n" << 0;return 0;}vector<int> steps = solve(n, k, vec);if (steps.size() > 0) {cout << "YES" << "\n" << steps.size() << "\n";for (int step : steps) cout << step << " ";cout << "\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 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 42 8 10 12 14 16 18 1 3 5 7 9 11 ... 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 10 12 14 16 18 13 15 17 4 6 8 ... |
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 334 336 338 340 342 344 346 34... 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 366 368 370 372 374 376 378 38... 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 454 456 458 460 462 464 466 46... 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 408 410 412 414 416 418 420 42... 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 2 4 6 8 10 12 14 16 18 20 22 2... 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 14501 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 13637 484 487 490 493 495 497 492 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 15413 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 14701 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 21508 484 487 490 493 495 497 137 14... 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 41789 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 13082 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 12735 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 12920 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 13889 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 31247 2 6 10 14 18 22 26 30 34 38 42... Truncated |