QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #286506 | #7960. 排序大师 | ucup-team022 | AC ✓ | 65ms | 3924kb | C++17 | 4.9kb | 2023-12-17 23:00:04 | 2023-12-17 23:00:04 |
Judging History
answer
#include<bits/stdc++.h>
#define int short
const int N=2055;
using namespace std;
int n;
int a[N],b[N];
int ia[N];
int v1[N],v2[N];
int calc(){
int res = 0;
for(int i=1;i<n;i++)if(a[i]!=a[i+1]-1)res++;
return res;
}
vector<vector<int>> res;
void swap(int i,int j,int k,int l){
int cnt = 0;
for(int o=1;o<i;o++)b[++cnt]=a[o];
for(int o=k;o<=l;o++)b[++cnt]=a[o];
for(int o=j+1;o<=k-1;o++)b[++cnt]=a[o];
for(int o=i;o<=j;o++)b[++cnt]=a[o];
for(int o=l+1;o<=n;o++)b[++cnt]=a[o];
assert(cnt==n);
for(int i=1;i<=n;i++)a[i]=b[i];
for(int i=1;i<=n;i++)ia[a[i]]=i;
res.push_back({i,j,k,l});
}
void solve(){
//freopen("data.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)ia[a[i]]=i;ia[n+1]=n+1;
int ans = 0;
while(calc()){
int m = 0;
int I=-1, J=-1, K=-1, L=-1;
priority_queue<int,vector<int>,greater<int>> q1, q2;
q1.push(2050);
q2.push(2050);
for(int i=1;i<=n;i++)v1[i]=v2[i]=0;
for(int i=1;i<n;i++){
int x=a[i],y=a[i+1];
int l=ia[y-1]+1,r=ia[x+1]-1;
if(l<=i&&i+1<=r){
int res = 0;
if(l!=1)res++;
if(r!=n)res++;
if(a[r]+1==a[l])res++;
if( m < res ){
m = res;
K = l;
J = i;
I = i+1;
L = r;
}
}
}
for(int i=1;i<=n;i++){
if(a[i]!=a[i-1]+1){//asi
int x = n+1, y = n+1;
if( a[i]!=1 )
x = ia[a[i]-1]+1;
if( i != 1 && a[i-1] != n )
y = ia[a[i-1]+1];
if( x == y ){
if(!v2[x])
q2.push(x),v2[x]=i;
}
else if(m<3){
if( x != n+1 && x >= i + 2 )
if( !v1[x])
q1.push(x),v1[x]=i;
if( y != n+1 && y >= i + 2 )
if( !v1[y] )
q1.push(y),v1[y]=i;
}
}
if(a[i]!=a[i+1]-1){//asj
if(m<3)while(q1.top() < i+2)q1.pop();
while(q2.top() < i+2)q2.pop();
int x = -1, y = -1;
if( a[i]!=n )
x = ia[a[i]+1]-1;
if( i != n && a[i+1] != 1 )
y = ia[a[i+1]-1];
if( x == y ){
if( x == -1 )continue;
if( q2.top() <= x ) {
if( m < 4 ){
m = 4;
I = q2.top();
J = i;
K = v2[q2.top()];
L = x;
}
}
if( q1.top() <= x ) {
if( m < 3 ){
m = 3;
I = q1.top();
J = i;
K = v1[q1.top()];
L = x;
}
}
}else{
if( q2.top() <= x ) {
if( m < 3 ){
m = 3;
I = q2.top();
J = i;
K = v2[q2.top()];
L = x;
}
}
if( q2.top() <= y ) {
if( m < 3 ){
m = 3;
I = q2.top();
J = i;
K = v2[q2.top()];
L = y;
}
}
if( q1.top() <= x ) {
if( m < 2 ){
m = 2;
I = q1.top();
J = i;
K = v1[q1.top()];
L = x;
}
}
if( q1.top() <= y ) {
if( m < 2 ){
m = 2;
I = q1.top();
J = i;
K = v1[q1.top()];
L = y;
}
}
}
}
if( m == 4 )break;
}
swap(K,J,I,L);
ans++;
}
cout << ans << endl;
for(auto x:res){
for(auto y:x)
cout << y << ' ';
cout << '\n';
}
}
main(){
ios::sync_with_stdio(0);
int _T=1;//cin>>_T;
while(_T--)solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3528kb
input:
1 1
output:
0
result:
ok orz U R the sorting master!
Test #2:
score: 0
Accepted
time: 64ms
memory: 3684kb
input:
1970 1452 1799 174 371 132 637 23 1510 1819 1794 1665 450 1183 564 1305 548 554 1310 701 1454 1843 1498 1040 1678 77 614 1928 1761 1718 1637 1853 1026 1804 1062 805 864 1859 586 663 346 335 681 152 1768 1639 1713 856 1401 1833 1350 1842 558 241 1829 802 581 1958 845 722 239 1793 1118 1251 1892 1949 ...
output:
981 54 78 79 466 18 68 69 759 33 57 58 1761 31 84 85 588 12 36 37 364 2 18 19 1620 38 55 56 151 17 85 86 388 14 30 31 1589 38 47 48 1521 18 57 58 433 9 22 23 1405 19 28 29 896 10 47 48 898 100 111 112 1542 95 124 125 1142 37 103 104 1352 34 120 121 1161 36 91 92 613 7 63 64 840 2...
result:
ok orz U R the sorting master!
Test #3:
score: 0
Accepted
time: 65ms
memory: 3848kb
input:
1983 1002 653 275 1324 1618 1893 1085 342 1858 355 1084 753 910 1417 841 1640 1620 613 311 456 225 51 1316 279 61 1261 68 870 320 147 148 959 49 1862 347 1765 880 293 746 849 488 233 1500 1825 22 547 1363 1034 136 151 1378 1756 1579 1957 647 336 1621 1543 637 214 1717 1871 1339 1732 975 565 919 424 ...
output:
988 183 647 650 1384 18 56 57 1055 31 35 36 533 37 84 85 1261 81 106 107 1276 19 81 82 438 17 43 44 287 32 43 44 488 24 82 83 1460 6 108 109 1432 27 38 39 48 20 66 67 1673 7 39 40 517 23 42 43 401 24 69 70 450 13 55 56 610 105 111 112 220 16 106 107 1750 56 82 83 1911 10 113 114 1...
result:
ok orz U R the sorting master!
Test #4:
score: 0
Accepted
time: 60ms
memory: 3924kb
input:
1967 172 148 690 1375 213 280 435 1727 1442 1579 1876 1455 1341 563 523 456 1712 312 1425 1890 616 1353 391 1957 1755 1155 1481 1402 532 1677 1328 1195 1940 156 188 965 937 1589 1429 1051 1025 1631 983 400 1029 1157 839 1594 1816 1911 46 609 1 1446 709 310 1706 410 1800 1725 124 199 529 131 1628 154...
output:
981 299 676 679 1887 16 134 135 981 61 79 80 1774 48 66 67 1357 6 61 62 987 35 42 43 906 57 83 84 208 8 74 75 1726 65 92 93 1575 59 72 73 978 57 60 61 1923 38 67 68 341 21 46 47 679 20 108 109 590 28 42 43 98 74 120 121 1495 17 182 183 611 441 484 485 1228 26 54 55 757 81 103 104 ...
result:
ok orz U R the sorting master!
Test #5:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
1961 1 2 3 4 5 6 7 8 9 10 11 12 13 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 ...
output:
1 14 283 506 1204
result:
ok orz U R the sorting master!
Test #6:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
1979 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...
output:
5 169 248 687 1815 221 643 1390 1976 266 347 1368 1542 376 397 1021 1130 456 536 644 712
result:
ok orz U R the sorting master!
Test #7:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
1971 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 162 163 164 165 166 167 168 169 170 171 172 17...
output:
20 87 102 633 1000 122 134 945 1093 235 264 714 1902 230 282 713 1540 373 394 509 1104 348 444 531 1775 414 454 674 705 375 470 830 838 322 408 1393 1474 340 396 515 1590 373 479 1069 1401 367 390 488 919 329 523 573 1638 590 772 909 1264 599 839 972 1388 321 658 1928 1955 323 808 96...
result:
ok orz U R the sorting master!
Test #8:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
1971 1 2 3 4 5 6 7 8 9 712 1843 131 132 1556 1557 1558 1559 1742 1743 1744 1745 1746 1747 1748 613 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 202 203 204 1767...
output:
100 11 11 271 1463 30 32 654 1357 27 30 80 1121 17 28 115 1396 44 46 206 1694 49 60 1711 1821 56 57 274 720 73 78 1127 1375 79 82 387 650 97 133 356 1354 89 98 184 1384 85 91 126 267 78 91 1579 1958 30 89 454 1144 39 39 120 1510 56 58 404 741 64 65 208 261 72 72 285 478 83 92 179 6...
result:
ok orz U R the sorting master!
Test #9:
score: 0
Accepted
time: 13ms
memory: 3608kb
input:
1973 1470 1471 1472 1473 1266 1959 1648 1649 1337 498 1080 875 1810 775 1448 1111 1112 1260 212 588 589 1128 51 1381 1442 700 701 660 1339 1850 1892 1893 905 1287 628 629 630 650 1262 1263 835 505 506 1773 173 98 1758 627 1677 1808 1809 1585 236 237 1458 1459 1460 1461 1907 1908 1909 1125 1474 37 19...
output:
500 9 24 1535 1603 33 35 631 1479 25 34 75 616 26 36 373 1312 19 30 493 760 13 21 53 1269 35 38 378 901 54 59 1066 1207 63 64 481 596 75 76 753 1117 78 96 162 1169 74 85 1076 1958 39 81 683 1597 12 39 274 1054 18 19 749 1391 24 25 1131 1846 54 55 929 1319 64 70 570 1314 73 82 252 1...
result:
ok orz U R the sorting master!
Test #10:
score: 0
Accepted
time: 45ms
memory: 3908kb
input:
1959 1 1009 1010 1461 171 1629 1761 1507 1508 1509 1621 992 1901 1154 841 736 737 738 333 1274 1652 1653 452 881 882 541 1247 1177 1662 965 966 1192 1193 1339 1831 1832 1031 1032 1928 105 1634 820 423 1103 1893 1894 163 1759 552 805 555 166 1199 1725 1463 23 1696 464 1787 1254 1655 1656 745 746 1388...
output:
824 8 87 809 1073 83 91 658 1808 122 159 772 1604 168 213 326 330 237 278 930 1888 274 303 463 1301 506 509 668 1214 509 520 618 664 792 817 1174 1904 533 888 1047 1069 1295 1355 1402 1417 908 1048 1049 1495 401 1065 1066 1666 644 848 1094 1779 635 918 919 1401 276 663 666 743 281 16...
result:
ok orz U R the sorting master!
Test #11:
score: 0
Accepted
time: 54ms
memory: 3684kb
input:
1966 1070 1605 424 264 1500 626 999 836 794 972 233 136 1256 1591 1271 417 678 235 854 1632 152 1895 257 258 469 1796 1811 1962 1207 934 1857 1089 1090 642 414 242 279 280 145 435 774 1351 1366 403 948 28 260 656 1467 1635 818 1061 1033 736 1706 619 228 1408 739 124 1554 688 1619 917 1332 1435 1015 ...
output:
936 17 179 1092 1238 326 482 1347 1409 346 761 953 1542 320 323 324 1711 310 541 542 1350 448 537 538 1716 26 51 55 1965 12 58 69 1525 3 42 43 720 25 64 65 1217 16 78 79 1735 69 127 128 1808 78 82 83 870 109 119 120 1621 12 159 160 1753 10 30 31 1303 33 60 61 127 2 50 51 468 26 64 ...
result:
ok orz U R the sorting master!
Test #12:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
2 2 1
output:
1 1 1 2 2
result:
ok orz U R the sorting master!
Test #13:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
3 1 3 2
output:
1 2 2 3 3
result:
ok orz U R the sorting master!
Test #14:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
10 10 1 8 5 7 9 4 3 2 6
output:
5 1 2 7 8 2 3 4 5 1 2 5 9 1 5 7 10 1 8 9 10
result:
ok orz U R the sorting master!
Test #15:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1967 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...
output:
0
result:
ok orz U R the sorting master!
Test #16:
score: 0
Accepted
time: 19ms
memory: 3628kb
input:
1999 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 1981 1980 1979 1978 1977 1976 1975 1974 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942 1941 ...
output:
999 1 1 3 3 1 3 5 5 1 5 7 7 1 7 9 9 1 9 11 11 1 11 13 13 1 13 15 15 1 15 17 17 1 17 19 19 1 19 21 21 1 21 23 23 1 23 25 25 1 25 27 27 1 27 29 29 1 29 31 31 1 31 33 33 1 33 35 35 1 35 37 37 1 37 39 39 1 39 41 41 1 41 43 43 1 43 45 45 1 45 47 47 1 47 49 49 1 49 51 51 1 51 53 5...
result:
ok orz U R the sorting master!
Test #17:
score: 0
Accepted
time: 23ms
memory: 3624kb
input:
1961 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 29 32 31 34 33 36 35 38 37 40 39 42 41 44 43 46 45 48 47 50 49 52 51 54 53 56 55 58 57 60 59 62 61 64 63 66 65 68 67 70 69 72 71 74 73 76 75 78 77 80 79 82 81 84 83 86 85 88 87 90 89 92 91 94 93 96 95 98 97 100 99 102...
output:
980 2 3 4 5 4 7 8 9 6 11 12 13 8 15 16 17 10 19 20 21 12 23 24 25 14 27 28 29 16 31 32 33 18 35 36 37 20 39 40 41 22 43 44 45 24 47 48 49 26 51 52 53 28 55 56 57 30 59 60 61 32 63 64 65 34 67 68 69 36 71 72 73 38 75 76 77 40 79 80 81 42 83 84 85 44 87 88 89 46 91 92 93 48 95 9...
result:
ok orz U R the sorting master!
Test #18:
score: 0
Accepted
time: 11ms
memory: 3716kb
input:
1996 3 2 1 6 5 4 9 8 7 12 11 10 15 14 13 18 17 16 21 20 19 24 23 22 27 26 25 30 29 28 33 32 31 36 35 34 39 38 37 42 41 40 45 44 43 48 47 46 51 50 49 54 53 52 57 56 55 60 59 58 63 62 61 66 65 64 69 68 67 72 71 70 75 74 73 78 77 76 81 80 79 84 83 82 87 86 85 90 89 88 93 92 91 96 95 94 99 98 97 102 101...
output:
665 1991 1993 1995 1995 1988 1992 1994 1994 1985 1989 1991 1991 1982 1986 1988 1988 1979 1983 1985 1985 1976 1980 1982 1982 1973 1977 1979 1979 1970 1974 1976 1976 1967 1971 1973 1973 1964 1968 1970 1970 1961 1965 1967 1967 1958 1962 1964 1964 1955 1959 1961 1961 1952 1956 1958 1958 19...
result:
ok orz U R the sorting master!
Test #19:
score: 0
Accepted
time: 8ms
memory: 3656kb
input:
1973 4 2 3 1 8 6 7 5 12 10 11 9 16 14 15 13 20 18 19 17 24 22 23 21 28 26 27 25 32 30 31 29 36 34 35 33 40 38 39 37 44 42 43 41 48 46 47 45 52 50 51 49 56 54 55 53 60 58 59 57 64 62 63 61 68 66 67 65 72 70 71 69 76 74 75 73 80 78 79 77 84 82 83 81 88 86 87 85 92 90 91 89 96 94 95 93 100 98 99 97 104...
output:
493 1966 1969 1972 1972 1962 1968 1971 1971 1958 1964 1967 1967 1954 1960 1963 1963 1950 1956 1959 1959 1946 1952 1955 1955 1942 1948 1951 1951 1938 1944 1947 1947 1934 1940 1943 1943 1930 1936 1939 1939 1926 1932 1935 1935 1922 1928 1931 1931 1918 1924 1927 1927 1914 1920 1923 1923 19...
result:
ok orz U R the sorting master!