Task: | Käännöt |
Sender: | Kemm1706 |
Submission time: | 2023-11-10 07:42:31 +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 'void rev(vl&, vl&, ll, ll, ll, vl&)': input/code.cpp:93:8: warning: unused variable 't' [-Wunused-variable] 93 | ll t, ii, jj; | ^ input/code.cpp: In function 'void view_tree(vitem&)': input/code.cpp:134:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::__cxx11::basic_string<char>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare] 134 | for (ll i = 0; i < v.size(); i++) | ~~^~~~~~~~~~ input/code.cpp: In function 'void solve_4(vl&, vl&, ll)': input/code.cpp:171:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::__cxx11::basic_string<char>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare] 171 | for (i = 0; i < v.size(); i++) |...
Code
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef vector<ll> vl;typedef pair <ll, ll> pll;typedef pair <string, pll> item;typedef vector <string> vs;typedef set <string> sstr;typedef vector <item> vitem;void outp(vl &a, ll n){for(ll i = 1; i <= n; i++)cout << a[i] << " ";}void print_op(vl &op){cout << "YES\n";cout << op.size() << '\n';for(auto x : op)cout << x << " ";cout << "\n";}void solve_2(vl &a, vl &p, ll n){ll p1, p2, i;vl op;for(i = n; i >= 1; i--){while(p[i] > i){p1 = p[i]; p2 = p1 - 1;op.push_back(p2);p[a[p2]] = p1;swap(a[p1], a[p2]);p[i]--;}while(p[i] < i){p1 = p[i]; p2 = p1 + 1;op.push_back(p1);p[a[p2]] = p1;swap(a[p1], a[p2]);p[i]++;}}print_op(op);}void solve_3(vl &a, vl &p, ll n){ll i;for(i = 1; i <= n; i++)if ((p[i] - i) % 2){cout << "NO\n";return;}ll p1, p2;vl op;for(i = n; i >= 1; i--){while(p[i] > i){p1 = p[i]; p2 = p1 - 2;op.push_back(p2);p[a[p2]] = p1;swap(a[p1], a[p2]);p[i] = p2;}while(p[i] < i){p1 = p[i]; p2 = p1 + 2;op.push_back(p1);p[a[p2]] = p1;swap(a[p1], a[p2]);p[i] = p2;}/*if (b){outp(a,n); cout << "\n";outp(p,n); cout << "\n";}*/}print_op(op);}void rev(vl &a, vl &p, ll n, ll k, ll stpos, vl &op){ll t, ii, jj;for (ii = stpos, jj = stpos + k - 1; ii < jj; ii++, jj--){swap(p[a[ii]], p[a[jj]]);swap(a[ii], a[jj]);}op.push_back(stpos);}void build_tree(ll n, ll k, vitem &v, sstr &ss){queue <ll> q;string s(n, '1'), t, r;ll i, parent;iota(s.begin(), s.end(), '1');v.push_back({s,{-1, -1}});q.push(0);ss.insert(s);while(!q.empty()){parent = q.front();r = v[parent].first;// cout << r << " " << "\n";q.pop();for(i = 0; i <= n - k; i++){t = r;reverse(t.begin()+i, t.begin() + i + k);if (ss.find(t) == ss.end()){ss.insert(t);v.push_back({t, {parent, i}});q.push(v.size() - 1);}}}}void view_tree(vitem &v){cout << v.size() << "\n";for (ll i = 0; i < v.size(); i++)cout << i << " " << v[i].first << setw(4) << v[i].second.first << setw(4) << v[i].second.second << "\n";}void solve_4(vl &a, vl &p, ll n){ll i, j, m;string s;vl op;for (i = n; i >= 7; i--){if(p[i] < i){if(p[i] == i - 2)rev(a, p, n, 4, p[i]-2, op);elseif (p[i] == i-1)rev(a, p, n, 4, p[i]-3, op);if(p[i] < 3)rev(a, p, n, 4, p[i], op);j = (i - p[i]) % 3;rev(a, p, n, 4, p[i]-j, op);/*outp(a, n); cout << "\n";outp(p, n); cout << "\n";*/while(p[i] < i)rev(a, p, n, 4, p[i], op);}}/*outp(a, n); cout << "\n";outp(p, n); cout << "\n";*/m = min(n, 6ll);for (i = 1; i <= m; i++)s += char(a[i] + '0');vitem v;sstr ss;build_tree(m, 4, v, ss);for (i = 0; i < v.size(); i++){auto str = v[i].first;if (str == s)break;}if (i == v.size())cout << "NO\n";else{// view_tree(v);j = i;while(j > 0){op.push_back(v[j].second.second+1);j = v[j].second.first;}print_op(op);}}void solve_5(vl &a, vl &p, ll n){ll i, j, k = 5, m = 7;vl op;string s;for (i = 1; i <= n; i++){if ((p[i] - i) % 2){cout << "NO\n";//cout << i << " " << p[i] << "\n";return;}}for(i = n; i > m; i--){if(p[i] < i){if(p[i] == i - 2)rev(a, p, n, k, p[i] - 3, op);else if(p[i] == i-4)rev(a, p, n, k, p[i], op);if(p[i] < 2)rev(a, p, n, k, p[i], op);j = (i - p[i]) % (k-1);if(j == 2)rev(a, p, n, k, p[i]-1, op);while(p[i] < i)rev(a, p, n, k, p[i], op);}}m = min(n,m);for (i = 1; i <= m; i++)s += char(a[i] + '0');vitem v;sstr ss;build_tree(m, k, v, ss);for(i = 0; i < v.size(); i++){auto str = v[i].first;if (str == s)break;}if(i == v.size())cout << "NO\n";else{// view_tree(v);j = i;while(j > 0){op.push_back(v[j].second.second+1);j = v[j].second.first;}print_op(op);}}int main(){int n, k;cin >> n >> k;vl a(n+1), p(n+1);for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)p[a[i]] = i;if (k == 2)solve_2(a, p, n);else if (k == 3)solve_3(a, p, n);else if (k == 4)solve_4(a, p, n);elsesolve_5(a, p, 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 14524 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 13714 483 485 488 491 494 497 486 48... 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 15350 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 14611 497 374 376 379 382 385 388 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 21665 483 485 488 491 494 497 135 13... 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 1 3 5 8 11 14 17 20 23 26 29 3... 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 13006 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 12911 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 12954 381 384 388 392 396 400 404 40... 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 13747 217 220 224 228 232 236 240 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 30881 1 4 8 12 16 20 24 28 32 36 40 ... Truncated |