Task: | Käännöt |
Sender: | maweiyin24562 |
Submission time: | 2023-11-09 01:03:54 +0200 |
Language: | C++ (C++17) |
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.11 s | 4 | details |
#29 | ACCEPTED | 0.07 s | 4 | details |
#30 | ACCEPTED | 0.02 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.07 s | 4 | details |
Compiler report
input/code.cpp: In function 'Node bfs()': input/code.cpp:261:1: warning: control reaches end of non-void function [-Wreturn-type] 261 | } | ^ input/code.cpp: In function 'Node2 bfs2()': input/code.cpp:298:1: warning: control reaches end of non-void function [-Wreturn-type] 298 | } | ^ input/code.cpp: In function 'void solve2()': input/code.cpp:22:13: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized] 22 | int pos; | ^~~ input/code.cpp: In function 'void solve3()': input/code.cpp:53:13: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized] 53 | int pos; | ^~~
Code
#include<bits/stdc++.h>//#include<windows.h>using namespace std;int a[509];int b[509];int n,m,k,inv;int ansList[1000009];bool inOrder(){for(int i=1;i<=n;i++){if(a[i]!=i)return false;}return true;}//----------------k=2----------------//void solve2(){cout<<"YES"<<endl;int pos;for(int i=1;i<=n;i++)if(a[i]!=i){for(int j=i+1;j<=n;j++){if(a[j]==i)pos=j;}for(int j=pos-1;j>=i;j--){m++;ansList[m]=j;swap(a[j],a[j+1]);}}cout<<m<<endl;for(int i=1;i<=m;i++){cout<<ansList[i]<<" ";}}//----------------k=3----------------//void solve3(){for(int i=1;i<=n;i+=2){if(a[i]%2==0){cout<<"NO"<<endl;return;}}for(int i=2;i<=n;i+=2){if(a[i]%2==1){cout<<"NO"<<endl;return;}}cout<<"YES"<<endl;int pos;for(int i=1;i<=n;i+=2)if(a[i]!=i){for(int j=i+2;j<=n;j++){if(a[j]==i)pos=j;}for(int j=pos-2;j>=i;j-=2){m++;ansList[m]=j;swap(a[j],a[j+2]);}}for(int i=2;i<=n;i+=2)if(a[i]!=i){for(int j=i+2;j<=n;j++){if(a[j]==i)pos=j;}for(int j=pos-2;j>=i;j-=2){m++;ansList[m]=j;swap(a[j],a[j+2]);}}cout<<m<<endl;for(int i=1;i<=m;i++){cout<<ansList[i]<<" ";}}//----------------k=4----------------//void reverse4(int p){swap(b[a[p]],b[a[p+3]]);swap(a[p],a[p+3]);swap(b[a[p+1]],b[a[p+2]]);swap(a[p+1],a[p+2]);}void debug(){for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;}void appendAns(int pos){m++;ansList[m]=pos;// Sleep(500);// debug();}bool inOrderLast5(){for(int i=n-4;i<n;i++){if(a[i+1]<a[i])return false;}return true;}void solve4(){if(inv%2==1){cout<<"NO"<<endl;return;}for(int i=1;i<=n-5;i++){if(b[i]==i)continue;while(b[i]-i>=4){int pos=b[i]-3;reverse4(pos);appendAns(pos);}if(b[i]-i==2){int pos=b[i]-1;reverse4(pos);appendAns(pos);}if(b[i]-i==1){int pos=b[i];reverse4(pos);appendAns(pos);ansList[m]=pos;pos=b[i]-2;reverse4(pos);appendAns(pos);}if(b[i]-i==3){reverse4(i);appendAns(i);}}int l=n-4;bool complete=false;int cnt=0;while(!complete&&m<=1000000){cnt++;int cmpM=m;for(int i=1;i<=5;i++){reverse4(l);appendAns(l);if(inOrderLast5()){complete=true;break;}reverse4(l+1);appendAns(l+1);if(inOrderLast5()){complete=true;break;}}if(complete)break;if(cnt%3==0){reverse4(l-1);appendAns(l-1);reverse4(l+1);appendAns(l+1);reverse4(l-2);appendAns(l-2);reverse4(l-1);appendAns(l-1);reverse4(l-2);appendAns(l-2);reverse4(l-1);appendAns(l-1);reverse4(l-3);appendAns(l-3);reverse4(l-2);appendAns(l-2);reverse4(l-1);appendAns(l-1);reverse4(l+1);appendAns(l+1);reverse4(l);appendAns(l);reverse4(l-3);appendAns(l-3);reverse4(l);appendAns(l);reverse4(l-1);appendAns(l-1);continue;}m=cmpM;reverse4(l-1);appendAns(l-1);reverse4(l);appendAns(l);reverse4(l-1);appendAns(l-1);reverse4(l);appendAns(l);reverse4(l+1);appendAns(l+1);reverse4(l-1);appendAns(l-1);}if(m>1000000){cout<<"NO"<<endl;return;}// debug();cout<<"YES"<<endl;cout<<m<<endl;for(int i=1;i<=m;i++){cout<<ansList[i]<<" ";}}//----------------k=5----------------//void reverse5(int p){swap(b[a[p]],b[a[p+4]]);swap(a[p],a[p+4]);swap(b[a[p+1]],b[a[p+3]]);swap(a[p+1],a[p+3]);}struct Node{int s[10];int mnode;int res[1009];void reverseNode5(int pos){swap(s[pos],s[pos+4]);swap(s[pos+1],s[pos+3]);}bool inOrder(){for(int i=1;i<n;i++){if(s[i]>s[i+1])return false;}return true;}};queue<Node>q;Node bfs(){Node nd;for(int i=1;i<=n;i++){nd.s[i]=a[i];}nd.mnode=0;q.push(nd);while(!q.empty()){Node u=q.front();q.pop();for(int i=1;i<=n-4;i++){Node v=u;v.reverseNode5(i);v.mnode++;v.res[v.mnode]=i;if(v.inOrder())return v;q.push(v);}}}struct Node2{int s[10];int mnode;int res[1009];void reverseNode5(int pos){swap(s[pos],s[pos+4]);swap(s[pos+1],s[pos+3]);}bool inOrder(){for(int i=1;i<9;i++){if(s[i]>s[i+1])return false;}return true;}};queue<Node2>q2;Node2 bfs2(){Node2 nd;for(int i=1;i<=9;i++){nd.s[i]=a[n-9+i];}nd.mnode=0;q2.push(nd);while(!q2.empty()){Node2 u=q2.front();q2.pop();for(int i=1;i<=5;i++){Node2 v=u;v.reverseNode5(i);v.mnode++;v.res[v.mnode]=i+n-9;if(v.inOrder())return v;q2.push(v);}}}void solve5(){for(int i=1;i<=n;i+=2){if(a[i]%2==0){cout<<"NO"<<endl;return;}}for(int i=2;i<=n;i+=2){if(a[i]%2==1){cout<<"NO"<<endl;return;}}if(inv%2==1){cout<<"NO"<<endl;return;}if(inOrder()){cout<<"YES\n0\n";return;}if(n==5){reverse5(1);appendAns(1);if(!inOrder()){cout<<"NO"<<endl;return;}cout<<"YES"<<endl;cout<<"1\n1";return;}if(n<10){cout<<"YES"<<endl;Node tmp=bfs();cout<<tmp.mnode<<endl;for(int i=1;i<=tmp.mnode;i++){cout<<tmp.res[i]<<" ";}return;}for(int i=1;i<n-8;i++){if(b[i]==i)continue;//o....x...while(b[i]-i>=5){int pos=b[i]-4;reverse5(pos);appendAns(pos);}//o.x....if(b[i]-i==2){int pos=b[i]-1;reverse5(pos);appendAns(pos);}if(b[i]-i==4){reverse5(i);appendAns(i);}// debug();}Node2 tmp2=bfs2();for(int i=1;i<=tmp2.mnode;i++){appendAns(tmp2.res[i]);}if(m>1000000){cout<<"NO"<<endl;return;}cout<<"YES"<<endl;cout<<m<<endl;for(int i=1;i<=m;i++){cout<<ansList[i]<<" ";}}//-----------------------------------//int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];for(int j=1;j<i;j++){if(a[j]>a[i]){inv++;}}b[a[i]]=i;}if(k==2){solve2();}else if(k==3){solve3();}else if(k==4){solve4();}else{solve5();}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 3 11 9 7 5 15 13 11 9 7 15 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 34 9 7 5 3 1 7 5 3 7 5 9 7 13 11 ... |
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 19 17 15 13 11 9 7 5 3 135... 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 10 1 2 1 2 1 2 1 2 1 2 |
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 14990 24 21 18 15 12 9 6 3 2 1 17 14... 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 14039 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 15686 227 224 221 218 215 212 209 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 14984 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 22036 338 335 332 329 326 323 320 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 42129 497 494 491 488 485 482 479 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 13426 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 13197 467 463 459 455 451 447 443 43... 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 13216 203 199 195 191 187 183 179 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 14075 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 31610 495 491 487 483 479 475 471 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 31493 495 491 487 483 479 475 471 46... Truncated |