QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#136167 | #2418. Inverted Deck | NightW0lf# | AC ✓ | 59ms | 11448kb | C++23 | 1.1kb | 2023-08-07 14:54:56 | 2023-08-07 14:54:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n; cin >> n;
int a[n + 1];
for(int i = 1; i <= n; i++) cin >> a[i];
int st = -1;
int en = -1;
for(int i = n; i > 1; i--) {
if(a[i] < a[i - 1]) {
st = i;
int prev = a[st];
while(st <= n and a[st] <= prev) {
prev = a[st];
st++;
}
st--;
prev = a[st];
en = st;
while(en >= 1 and a[en] >= prev) {
prev = a[en];
en--;
}
en++;
break;
}
}
if(st != -1) {
int l = en;
int r = st;
while(l < r) {
swap(a[l], a[r]);
l++;
r--;
}
}
else {
st = n; en = n;
}
for(int i = 1; i < n; i++) {
if(a[i] > a[i + 1]) {
cout << "impossible\n";
return 0;
}
}
cout << en << " " << st << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3468kb
input:
10 1 1 3 2 1 1 1 1 1 1
output:
3 10
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
6 1 1 3 2 4 4
output:
3 4
result:
ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
10 1 2 3 6 5 4 7 8 10 9
output:
impossible
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
10 1 2 3 6 5 2 7 8 9 10
output:
impossible
result:
ok
Test #5:
score: 0
Accepted
time: 59ms
memory: 11232kb
input:
1000000 4 40 43 52 59 73 112 121 171 172 176 178 191 213 231 232 246 248 260 281 289 293 299 304 305 313 322 328 334 342 350 354 365 368 375 394 396 415 423 438 442 458 477 481 482 488 509 542 551 560 568 577 600 606 607 618 621 624 630 633 641 648 652 664 670 674 700 714 722 731 738 744 752 759 762...
output:
42808 913472
result:
ok
Test #6:
score: 0
Accepted
time: 53ms
memory: 11396kb
input:
1000000 409 570 1267 1629 3963 5616 6811 7182 7516 10592 13922 13942 14226 15251 15522 16452 16764 19460 20246 20620 23417 24490 27014 27448 27818 28120 28340 29183 30471 30786 30808 31305 31978 32959 33442 33935 33993 34654 35001 36233 37047 38219 38598 38930 38974 41456 41461 43819 46904 48287 498...
output:
impossible
result:
ok
Test #7:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
10000 51635 207636 237289 385339 516068 567003 663284 736518 805572 976528 1368937 1573659 1608327 1614833 1642465 1928162 2181078 2342076 2380766 2416376 2435735 2500318 2564312 2952411 3174749 3302393 3305579 3326493 3333878 3407137 3428011 3556833 3574078 3597129 3692125 3824718 3957636 3970682 4...
output:
2184 8082
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
10000 417202643 417196298 417003857 416929882 416907389 416722644 416706851 416588892 416127622 415955312 415904698 415693324 415596496 415536167 415516089 415488214 415434479 415353544 415306444 415281695 415065007 414820717 414807870 414656655 414644999 414423971 414324747 414319714 414251770 4142...
output:
1 4198
result:
ok
Test #9:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
10000 51635 207636 237289 385339 516068 567003 663284 736518 805572 976528 1368937 1573659 1608327 1614833 1642465 1928162 2181078 2342076 2380766 2416376 2435735 2500318 2564312 2952411 3174749 3302393 3305579 3326493 3333878 3407137 3428011 3556833 3574078 3597129 3692125 3824718 3957636 3970682 4...
output:
1160 10000
result:
ok
Test #10:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
10000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 999921698 999872822 999846654 999790817 999628828 999568776 999516877 999386244 999297091 999206084 999075511 999057319 999022247 998969445 998780767 998725036 998685493 998669764 9986...
output:
1 10000
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
10000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 999921698 999872822 999846654 999790817 999628828 999568776 999516877 999386244 999297091 999206084 999075511 999057319 999022247 998969445 998780767 998725036 998685493 998669764 9986...
output:
impossible
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
7 10 13 19 19 15 14 20
output:
3 6
result:
ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
1 259008492
output:
1 1
result:
ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 3472kb
input:
10 213907531 147159919 130213023 225162936 294656754 431580329 531314752 608402148 734023603 837656511
output:
1 3
result:
ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
100 2974541 5715977 31739767 38827494 43208542 69143925 73275778 77427283 92661929 112260177 117360051 121516194 130780962 134853762 137007504 141745564 159756719 164483434 176633748 194468951 202626633 203058293 211715690 225557411 413490905 395757369 389688761 374756244 366697750 366439910 3642026...
output:
25 46
result:
ok
Test #16:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
1000 533422 979129 1215977 2033560 3748708 6028322 9590414 10686497 11560880 12327115 12946913 14533082 15677014 16073728 16262838 17250301 19272219 19645468 19944841 20387854 20727789 22028549 25647922 27452442 28365463 28493781 29342822 29767040 32161222 34192156 35785135 39005124 39163159 4220906...
output:
55 324
result:
ok
Test #17:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
10000 169644 234020 245764 354832 407495 564016 711991 786516 846011 896198 1057461 1160847 1286539 1309402 1510395 1620186 1639228 1756496 1768619 1944251 1990337 1992047 1997003 2087591 2103446 2115688 2453532 2481415 2552222 2597324 2609563 2621944 2949059 3066250 3078893 3159209 3445504 3461964 ...
output:
7667 7922
result:
ok
Test #18:
score: 0
Accepted
time: 8ms
memory: 4252kb
input:
100000 22617 31059 39740 40330 51674 60639 75551 81720 86220 91546 109789 125817 125872 140620 146533 163539 174809 177196 195217 224866 226174 243544 250455 252859 273026 277807 310738 317919 321050 321718 322551 344531 348555 367873 371125 372487 391229 413946 428584 429656 430853 433116 436845 44...
output:
10431 71708
result:
ok
Test #19:
score: 0
Accepted
time: 42ms
memory: 11448kb
input:
1000000 1558 1990 2632 3261 3586 3829 4308 5932 6840 7336 8765 8850 10516 12598 13165 14364 15765 16306 19543 19722 20253 22485 22751 24965 26156 26356 30683 31025 31453 32404 33014 34217 35969 36809 37993 39058 41404 41676 42174 42819 44304 44364 45743 46347 47851 53644 55585 56635 58227 60071 6046...
output:
847683 970517
result:
ok
Test #20:
score: 0
Accepted
time: 1ms
memory: 3376kb
input:
1 1
output:
1 1
result:
ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
10 1 1 2 2 2 2 2 2 2 2
output:
10 10
result:
ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
100 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 6 6 7 7 6 6 6 6 6 6 6 6 7 7 7 8 8 8 8 8 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11
output:
54 63
result:
ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 3472kb
input:
1000 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15...
output:
722 994
result:
ok
Test #24:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
10000 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14...
output:
5934 8582
result:
ok
Test #25:
score: 0
Accepted
time: 3ms
memory: 4260kb
input:
100000 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 7 7 7 7 7 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 ...
output:
17091 99116
result:
ok
Test #26:
score: 0
Accepted
time: 42ms
memory: 11352kb
input:
1000000 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 13 13 13 1...
output:
797265 863819
result:
ok
Test #27:
score: 0
Accepted
time: 1ms
memory: 3380kb
input:
10 2 2 2 2 2 2 2 2 1 1
output:
1 10
result:
ok
Test #28:
score: 0
Accepted
time: 1ms
memory: 3412kb
input:
100 11 11 11 11 11 11 11 11 10 10 10 10 10 10 10 10 10 10 10 10 9 9 9 9 9 9 9 9 9 8 8 8 8 8 7 7 7 7 7 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
output:
1 100
result:
ok
Test #29:
score: 0
Accepted
time: 1ms
memory: 3384kb
input:
1000 101 101 101 101 101 101 100 100 100 100 100 100 100 100 100 100 99 99 99 99 99 99 99 99 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 97 97 97 97 97 97 96 96 96 96 96 96 96 96 96 96 95 95 95 95 95 95 95 95 95 95 95 95 94 94 94 94 94 94 94 94 94 94 93 93 93 93 93 93 93 93 93 93 93 92 92 92 92 ...
output:
1 1000
result:
ok
Test #30:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
10000 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1000 1000 1000 1000 1000 1000 1000 999 999 999 999 999 999 999 999 999 999 998 998 998 998 998 998 998 998 998 998 998 998 998 998 998 998 998 998 997 997 997 997 997 997 997 997 996 996 996 996 996 996 996 996 996 996 996 996 99...
output:
1 10000
result:
ok
Test #31:
score: 0
Accepted
time: 3ms
memory: 4200kb
input:
100000 10001 10001 10001 10001 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9998 9998 9998 9998 9998 9998 9998 9998 9998 9997 9997 9997 9997 9997 9997 9997 9997 9997 9997 9997 9997 9997 9...
output:
1 100000
result:
ok
Test #32:
score: 0
Accepted
time: 45ms
memory: 11184kb
input:
1000000 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99998 99998 99998 99998 99998 99998 99998 99998 99998 99997 99997...
output:
1 1000000
result:
ok
Test #33:
score: 0
Accepted
time: 1ms
memory: 3472kb
input:
6 9 1 8 2 7 3
output:
impossible
result:
ok
Test #34:
score: 0
Accepted
time: 1ms
memory: 3464kb
input:
3 1 2 3
output:
3 3
result:
ok