QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #288097 | #7960. 排序大师 | zhouhuanyi | AC ✓ | 2ms | 3928kb | C++20 | 1.2kb | 2023-12-21 20:49:52 | 2023-12-21 20:49:54 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define N 2001
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int l1,r1,l2,r2;
};
reads tong[N+1];
int n,length,leng,ps[N+1],st[N+1],p[N+1];
void solve(int l1,int r1,int l2,int r2)
{
leng=-1,tong[++length]=(reads){l1,r1,l2,r2};
for (int i=0;i<=l1-1;++i) st[++leng]=p[i];
for (int i=l2;i<=r2;++i) st[++leng]=p[i];
for (int i=r1+1;i<=l2-1;++i) st[++leng]=p[i];
for (int i=l1;i<=r1;++i) st[++leng]=p[i];
for (int i=r2+1;i<=n+1;++i) st[++leng]=p[i];
for (int i=0;i<=n+1;++i) p[i]=st[i];
return;
}
int main()
{
int x,y;
n=read(),p[0]=0,p[n+1]=n+1;
for (int i=1;i<=n;++i) p[i]=read();
while (1)
{
x=y=-1;
for (int i=0;i<=n+1;++i) ps[p[i]]=i;
for (int i=0;i<=n+1;++i)
if (ps[i]!=i)
{
x=i;
break;
}
if (x==-1) break;
for (int i=n+1;i>=1;--i)
if (ps[i]<ps[x])
{
y=i;
break;
}
solve(ps[x-1]+1,ps[y],ps[x],ps[y+1]-1);
}
printf("%d\n",length);
for (int i=1;i<=length;++i) printf("%d %d %d %d\n",tong[i].l1,tong[i].r1,tong[i].l2,tong[i].r2);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
input:
1 1
output:
0
result:
ok orz U R the sorting master!
Test #2:
score: 0
Accepted
time: 2ms
memory: 3812kb
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 1 209 394 1342 2 243 606 1594 3 269 698 1430 4 1595 1758 1970 5 419 988 1968 6 1566 1721 1966 7 10 37 1306 8 439 905 1944 9 296 917 1965 10 1037 1722 1963 11 256 355 1961 12 1263 1703 1894 13 492 1154 1726 14 38 39 1087 15 104 122 428 16 462 1095 1725 17 250 970 1355 18 576 1012 1734 19 130 239 ...
result:
ok orz U R the sorting master!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
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 1 768 844 1183 2 302 542 858 3 1184 1874 1983 4 10 1560 1981 5 102 201 1980 6 754 1415 1786 7 1003 1279 1785 8 193 471 1465 9 283 934 1559 10 1787 1935 1978 11 756 1102 1975 12 26 30 125 13 1364 1507 1974 14 1270 1535 1973 15 254 1437 1971 16 520 1696 1970 17 101 1583 1969 18 186 1262 1525 19 93...
result:
ok orz U R the sorting master!
Test #4:
score: 0
Accepted
time: 2ms
memory: 3928kb
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 1 24 53 926 2 705 1775 1967 3 214 468 520 4 521 1613 1966 5 174 419 1290 6 1606 1645 1811 7 63 218 1844 8 63 380 1909 9 101 203 1227 10 1229 1774 1964 11 444 480 1452 12 356 606 1449 13 1454 1546 1961 14 367 1665 1955 15 1674 1836 1954 16 607 653 1953 17 765 1150 1952 18 46 1838 1951 19 542 1598...
result:
ok orz U R the sorting master!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3860kb
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: 0ms
memory: 3744kb
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 340 687 738 266 1161 1722 1976 360 1162 1462 1542 376 397 1021 1130 456 536 644 712
result:
ok orz U R the sorting master!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3744kb
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 126 633 901 122 357 822 1542 178 208 301 1785 230 330 369 621 241 1459 1615 1765 264 700 754 1217 334 1266 1403 1871 343 799 829 1965 386 582 937 1314 415 463 483 1752 455 481 671 1003 642 696 870 1642 722 1114 1146 1763 724 900 1615 1623 758 789 953 993 840 1056 1105 1617 864 912 932 1142 871...
result:
ok orz U R the sorting master!
Test #8:
score: 0
Accepted
time: 0ms
memory: 3852kb
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 10 39 1173 1971 12 684 1550 1742 17 100 653 1957 18 85 466 733 23 114 296 1169 25 474 696 1507 26 170 441 1955 37 1465 1762 1930 53 238 345 730 55 373 1242 1542 63 63 132 1358 68 184 208 1625 77 209 789 1644 81 710 782 1925 84 220 491 1439 93 540 948 1441 107 1789 1834 1903 109 705 1377 1842 113...
result:
ok orz U R the sorting master!
Test #9:
score: 0
Accepted
time: 1ms
memory: 3856kb
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 1 157 159 950 5 125 179 1929 6 96 737 773 7 777 1697 1972 8 325 570 1967 9 62 937 1966 10 76 1769 1964 12 220 1763 1962 14 725 1175 1961 16 495 828 1631 17 118 297 448 18 57 1230 1630 19 810 1171 1554 20 494 803 1552 21 248 679 1209 22 463 1216 1804 24 438 1677 1959 26 264 1491 1952 27 417 1024 ...
result:
ok orz U R the sorting master!
Test #10:
score: 0
Accepted
time: 1ms
memory: 3808kb
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 2 328 409 1365 3 181 291 849 5 409 857 1959 6 514 687 1958 7 268 1103 1956 8 172 201 1644 9 141 159 1400 11 591 1710 1955 12 781 985 1954 13 406 515 1952 14 68 294 384 16 385 672 1489 17 1394 1399 1487 19 55 150 1232 20 861 1087 1486 21 1490 1913 1951 22 106 200 1207 23 449 584 1453 24 295 1900 ...
result:
ok orz U R the sorting master!
Test #11:
score: 0
Accepted
time: 1ms
memory: 3888kb
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 1 661 857 1142 2 509 641 1937 3 505 1735 1966 4 206 1744 1963 5 277 1376 1961 6 460 677 1204 7 1205 1871 1959 8 601 1031 1551 9 210 1526 1957 10 35 1543 1854 11 405 1560 1852 12 537 1143 1851 13 830 1527 1850 14 199 540 1849 15 140 761 1518 16 959 1236 1318 17 28 594 1517 18 210 271 1801 20 1505...
result:
ok orz U R the sorting master!
Test #12:
score: 0
Accepted
time: 0ms
memory: 3740kb
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: 3780kb
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: 3912kb
input:
10 10 1 8 5 7 9 4 3 2 6
output:
5 1 1 2 10 2 5 8 9 3 3 5 7 4 4 6 8 5 6 7 7
result:
ok orz U R the sorting master!
Test #15:
score: 0
Accepted
time: 0ms
memory: 3860kb
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: 1ms
memory: 3864kb
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 1999 1999 2 2 1998 1998 3 3 1997 1997 4 4 1996 1996 5 5 1995 1995 6 6 1994 1994 7 7 1993 1993 8 8 1992 1992 9 9 1991 1991 10 10 1990 1990 11 11 1989 1989 12 12 1988 1988 13 13 1987 1987 14 14 1986 1986 15 15 1985 1985 16 16 1984 1984 17 17 1983 1983 18 18 1982 1982 19 19 1981 1981 20 20 1980...
result:
ok orz U R the sorting master!
Test #17:
score: 0
Accepted
time: 2ms
memory: 3756kb
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 1 1 2 3 2 2 3 5 4 4 5 7 6 6 7 9 8 8 9 11 10 10 11 13 12 12 13 15 14 14 15 17 16 16 17 19 18 18 19 21 20 20 21 23 22 22 23 25 24 24 25 27 26 26 27 29 28 28 29 31 30 30 31 33 32 32 33 35 34 34 35 37 36 36 37 39 38 38 39 41 40 40 41 43 42 42 43 45 44 44 45 47 46 46 47 49 48 48 49 51 50 50 51 53 52 ...
result:
ok orz U R the sorting master!
Test #18:
score: 0
Accepted
time: 1ms
memory: 3796kb
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 1 1 3 5 2 2 4 8 5 5 7 11 8 8 10 14 11 11 13 17 14 14 16 20 17 17 19 23 20 20 22 26 23 23 25 29 26 26 28 32 29 29 31 35 32 32 34 38 35 35 37 41 38 38 40 44 41 41 43 47 44 44 46 50 47 47 49 53 50 50 52 56 53 53 55 59 56 56 58 62 59 59 61 65 62 62 64 68 65 65 67 71 68 68 70 74 71 71 73 77 74 74 76 ...
result:
ok orz U R the sorting master!
Test #19:
score: 0
Accepted
time: 1ms
memory: 3812kb
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 1 1 4 7 2 2 5 11 6 6 9 15 10 10 13 19 14 14 17 23 18 18 21 27 22 22 25 31 26 26 29 35 30 30 33 39 34 34 37 43 38 38 41 47 42 42 45 51 46 46 49 55 50 50 53 59 54 54 57 63 58 58 61 67 62 62 65 71 66 66 69 75 70 70 73 79 74 74 77 83 78 78 81 87 82 82 85 91 86 86 89 95 90 90 93 99 94 94 97 103 98 98...
result:
ok orz U R the sorting master!