QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #830189 | #9914. 前往何方 | kgqy | 99.6648 | 280ms | 6832kb | C++14 | 1.9kb | 2024-12-24 16:36:48 | 2024-12-24 16:36:49 |
Judging History
answer
#include<bits/stdc++.h>
#include "wheretoreach.h"
using namespace std;
int al,ed;
int tims;
vector<int> vec;
vector<int> tv,ct;
int rk[100005];
int vis[100005];
int tadd(int u){
vis[rk[u]]=1;
return add(rk[u]);
}
int tremove(int u){
if(!vis[rk[u]]) return 0;
vis[rk[u]]=0;
return remove(rk[u]);
}
void treport(int u,int v){
tims++;
report(rk[u],rk[v]);
}
void bs(int l,int r,vector<int> nt){
if(!nt.size()) return;
if(tims==al-1) return;
// printf("lr %d %d\nnt:",l,r);
// for(int i=0;i<nt.size();i++) printf("%d ",nt[i]);puts("");
if(l==r){
for(int i=0;i<nt.size();i++){
// printf("REPORTER %d %d\n",nt[i],tv[l]);
treport(nt[i],tv[l]);
}
return;
}
vector<int> lt,rt;
int mid=(l+r)>>1;
if(l!=0||r!=ed)
for(int i=l;i<=mid;i++) tadd(tv[i]);
for(int i=0;i<nt.size();i++){
int p=tadd(nt[i]);
if(p>1) lt.push_back(nt[i]);
else rt.push_back(nt[i]);
tremove(nt[i]);
}
for(int i=l;i<=mid;i++) tremove(tv[i]);
bs(l,mid,lt);
if(tims==al-1) return;
if(lt.size()&&rt.size()+tims<al-1){
for(int i=mid+1;i<=r;i++) tadd(tv[i]);
for(int i=0;i<lt.size();i++){
int p=tadd(lt[i]);
if(p>1) rt.push_back(lt[i]);
tremove(lt[i]);
}
for(int i=mid+1;i<=r;i++) tremove(tv[i]);
}
bs(mid+1,r,rt);
}
void mian(){
tv.clear();ct.clear();
for(int i=1;i<=al;i++) vis[i]=0;
for(int i=0;i<vec.size();i++){
int p=tadd(vec[i]);
if(p>1) ct.push_back(vec[i]),tremove(vec[i]);
else tv.push_back(vec[i]);
}
// for(int i=0;i<tv.size();i++) printf("%d ",tv[i]);puts("");
if(!ct.size()) return vec.clear();
int mid=(tv.size()-1)>>1;
ed=tv.size()-1;
for(int i=mid+1;i<tv.size();i++) tremove(tv[i]);
bs(0,tv.size()-1,ct);
vec=ct;
if(tims==al-1) vec.clear();
}
void solve(int n){
al=n;
for(int i=1;i<=n;i++) rk[i]=i,vec.push_back(i);
mt19937 lrher(time(0));
shuffle(rk+1,rk+1+n,lrher);
while(vec.size()) mian();
if(tims!=al-1) assert(0);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 6ms
memory: 4256kb
input:
500 310 77 468 235 218 93 58 406 223 334 159 243 204 48 144 107 492 288 447 165 102 407 340 299 450 126 140 234 209 62 111 204 453 306 4 476 126 358 183 317 360 489 149 158 232 22 326 372 92 383 410 24 199 14 401 480 69 329 192 167 409 152 426 354 435 60 146 404 334 187 208 305 123 55 30 79 469 72 2...
output:
19002 1
result:
ok Accepted. 19002 queries used.
Test #2:
score: 10
Accepted
time: 6ms
memory: 4228kb
input:
500 60 412 153 399 248 57 59 152 349 209 303 223 412 181 6 375 158 63 490 178 176 462 313 417 187 411 19 431 30 448 302 264 252 56 427 269 53 429 147 358 417 154 21 326 358 157 450 340 256 324 489 160 193 72 491 65 259 17 153 368 484 55 294 305 27 420 144 119 229 70 22 32 90 432 150 356 398 42 473 2...
output:
18870 1
result:
ok Accepted. 18870 queries used.
Test #3:
score: 10
Accepted
time: 6ms
memory: 4252kb
input:
500 434 238 470 430 111 20 414 129 408 188 220 491 483 375 203 240 315 401 344 357 315 429 246 486 291 403 465 23 477 67 155 34 27 457 349 305 220 496 384 242 87 8 74 141 458 119 206 177 246 125 332 461 111 343 413 210 280 405 288 407 60 84 70 140 31 482 110 473 94 6 361 294 96 279 438 428 295 379 1...
output:
19068 1
result:
ok Accepted. 19068 queries used.
Test #4:
score: 10
Accepted
time: 6ms
memory: 4524kb
input:
500 358 385 92 131 274 356 210 2 35 490 296 407 58 286 37 111 60 291 199 463 325 346 356 309 169 213 165 28 373 176 80 274 331 446 358 345 229 75 426 264 223 318 487 478 415 183 418 339 405 133 180 441 485 41 493 445 187 238 249 76 7 419 264 105 103 321 288 287 20 1 172 391 365 88 247 396 402 206 31...
output:
19282 1
result:
ok Accepted. 19282 queries used.
Test #5:
score: 10
Accepted
time: 3ms
memory: 4472kb
input:
500 457 191 315 191 191 459 163 191 416 191 217 191 279 191 75 191 7 191 206 191 191 317 108 191 223 191 225 191 191 414 196 191 191 248 191 264 38 191 15 191 406 191 191 480 454 191 191 212 99 191 321 191 415 191 191 240 298 191 468 191 191 187 191 340 191 19 170 191 191 430 191 496 222 191 191 386...
output:
11448 1
result:
ok Accepted. 11448 queries used.
Test #6:
score: 10
Accepted
time: 3ms
memory: 5976kb
input:
500 136 391 151 227 114 291 227 444 481 304 227 139 450 55 227 117 109 343 441 227 398 436 248 181 485 227 167 358 227 174 228 206 107 213 227 331 279 447 321 65 208 440 288 183 470 227 227 380 427 227 408 162 493 196 56 378 434 266 227 9 54 227 227 491 227 469 151 191 92 496 265 227 242 296 456 349...
output:
16162 1
result:
ok Accepted. 16162 queries used.
Test #7:
score: 10
Accepted
time: 6ms
memory: 6056kb
input:
500 32 112 430 35 282 448 388 442 25 72 281 420 9 27 245 294 28 470 119 144 343 6 4 31 236 429 230 264 285 469 463 303 365 443 169 297 374 7 345 475 420 143 388 31 403 175 51 67 288 311 86 473 349 488 239 105 402 328 9 164 150 370 205 260 439 11 62 245 115 409 272 439 319 142 466 409 407 478 89 197 ...
output:
18138 1
result:
ok Accepted. 18138 queries used.
Test #8:
score: 10
Accepted
time: 6ms
memory: 4260kb
input:
500 237 221 171 286 204 484 179 375 401 385 84 107 167 463 459 69 326 325 234 72 500 138 291 498 80 204 339 383 369 240 344 335 68 327 193 7 294 389 364 102 369 69 495 187 445 386 18 6 144 25 287 205 356 347 143 49 90 74 450 386 55 477 480 11 309 227 63 332 257 23 414 431 207 151 449 19 393 118 441 ...
output:
18886 1
result:
ok Accepted. 18886 queries used.
Subtask #2:
score: 20
Accepted
Test #9:
score: 20
Accepted
time: 47ms
memory: 4880kb
input:
2500 887 818 1296 878 1605 2107 803 2410 1919 1135 860 1160 1364 2414 1375 500 894 2173 2322 2449 211 1732 1821 573 413 1556 1574 1977 709 162 2002 1577 1626 1895 1563 688 2151 2293 661 69 317 1170 2335 1549 1481 1349 1500 779 1593 735 1824 2380 639 2334 1496 2335 1956 1384 2476 1583 1035 163 720 70...
output:
124280 2
result:
ok Accepted. 124280 queries used.
Test #10:
score: 20
Accepted
time: 48ms
memory: 4580kb
input:
2500 1186 1927 2337 1044 1440 973 1563 297 1771 1852 921 834 1121 2156 679 211 1146 2132 1537 825 821 1240 1372 133 77 174 2453 1807 1357 550 1620 2020 2024 528 1666 1812 720 900 1243 2090 1665 1738 445 1306 2039 1721 1370 930 948 2331 521 121 1581 2059 1752 2039 218 785 988 2477 121 2462 578 503 11...
output:
125218 2
result:
ok Accepted. 125218 queries used.
Test #11:
score: 20
Accepted
time: 49ms
memory: 4892kb
input:
2500 778 2243 2254 352 1211 233 607 2369 1908 1499 2053 1966 1790 438 1032 703 898 2 1461 1159 1757 2022 1030 753 1123 2124 2346 528 1604 1207 341 1255 2435 999 526 888 1881 1472 251 618 1381 1303 981 1982 130 809 1623 1399 2229 1011 1836 1243 277 2147 588 1119 1980 1235 19 1795 734 2088 845 1841 89...
output:
124208 2
result:
ok Accepted. 124208 queries used.
Test #12:
score: 20
Accepted
time: 49ms
memory: 4580kb
input:
2500 1883 628 95 1337 203 1367 2078 760 115 2231 786 1486 931 248 2064 1215 336 193 175 1360 844 284 1105 102 2413 1374 2017 399 1321 947 2194 1969 2305 390 2193 1452 48 534 974 1439 2133 1727 2209 216 631 861 2279 1004 241 1797 2298 59 790 186 897 855 460 620 841 1701 1709 1541 403 95 909 1553 975 ...
output:
125228 2
result:
ok Accepted. 125228 queries used.
Test #13:
score: 20
Accepted
time: 22ms
memory: 4836kb
input:
2500 2420 40 1914 40 1373 40 817 40 985 40 40 237 40 1843 40 839 1673 40 40 1611 1631 40 40 1805 2378 40 391 40 40 1198 40 622 1232 40 40 1799 648 40 40 760 40 1163 1883 40 1033 40 2221 40 40 1020 1136 40 493 40 40 2379 404 40 40 84 2215 40 1746 40 40 2259 40 1966 1050 40 112 40 1637 40 40 196 1795 ...
output:
69274 2
result:
ok Accepted. 69274 queries used.
Test #14:
score: 20
Accepted
time: 36ms
memory: 4604kb
input:
2500 1402 1724 1724 1895 2497 667 190 1343 1690 1724 807 612 1724 2012 1581 1724 1973 1724 385 2129 474 1736 1724 1671 1724 807 1724 232 1096 447 1928 1724 1724 2404 868 579 1724 1779 1724 1167 793 1542 684 1469 874 785 58 1724 2108 1724 1724 1470 2269 2042 1724 1346 2451 8 250 1393 751 1825 2353 11...
output:
102850 2
result:
ok Accepted. 102850 queries used.
Test #15:
score: 20
Accepted
time: 42ms
memory: 6508kb
input:
2500 107 684 1016 2062 840 2253 1686 2339 2322 150 2143 535 918 623 2360 1782 1109 1519 1698 1588 1379 329 2119 1632 733 1390 557 1680 1013 2386 1767 268 2346 154 674 465 1757 549 801 1875 1090 1020 1521 2205 1861 129 2144 613 552 1341 970 855 41 1750 896 23 2106 1953 1656 1861 2408 1509 151 1301 70...
output:
117478 2
result:
ok Accepted. 117478 queries used.
Test #16:
score: 20
Accepted
time: 47ms
memory: 4928kb
input:
2500 810 880 2265 2017 1745 430 2088 1832 491 2189 1915 2457 1846 1557 118 1427 1269 980 1427 2245 590 709 2041 1179 1161 57 2069 1870 1950 2333 1378 885 385 195 1277 524 458 1603 1025 1041 646 1451 2036 903 2499 1796 823 1850 1030 957 1584 2049 67 1325 386 1257 1095 1452 1078 143 709 978 225 1771 1...
output:
123574 2
result:
ok Accepted. 123574 queries used.
Subtask #3:
score: 69.6648
Acceptable Answer
Test #17:
score: 70
Accepted
time: 272ms
memory: 6028kb
input:
10000 6139 8917 131 5800 5366 5247 1298 5035 3966 3518 4889 7202 6547 1919 5829 9494 8012 6029 3868 6403 1909 8116 5734 6122 2683 4779 9275 6673 7433 9042 7646 2032 3547 6306 1943 8382 4061 6428 8240 3548 460 2795 3451 4320 5904 6627 8709 7621 8706 3534 748 4873 8101 4261 5359 3304 6254 4687 6492 53...
output:
594094 3
result:
ok Accepted. 594094 queries used.
Test #18:
score: 69.6648
Acceptable Answer
time: 277ms
memory: 5776kb
input:
10000 2681 8564 3271 4429 6658 3180 2428 7273 8907 2727 5939 1929 2539 1768 7178 7722 3420 8555 1346 811 3608 2345 6181 6871 5539 8722 4731 8049 8581 7954 3979 384 9678 3503 7073 6690 240 7950 16 7004 1591 8818 5422 3777 3382 852 1805 6181 1965 2752 6507 7858 9373 4985 6912 2901 9954 4194 1029 7631 ...
output:
601676 3
result:
points 0.9952114286 601676 queries used.
Test #19:
score: 70
Accepted
time: 277ms
memory: 6048kb
input:
10000 1342 5746 3635 7521 8778 5159 4764 6368 6494 390 174 9762 1667 1808 8257 9287 8449 8308 8952 6760 4300 8776 8608 304 6035 8674 3012 2422 326 676 2883 2429 5929 6038 4183 6495 3578 6621 9215 894 6669 521 3507 7339 1972 75 9478 8427 9802 5494 2085 6339 2258 6254 9484 4048 4093 3234 4063 7612 695...
output:
597656 3
result:
ok Accepted. 597656 queries used.
Test #20:
score: 70
Accepted
time: 278ms
memory: 5816kb
input:
10000 960 6995 1934 8650 2086 4139 5869 6110 9863 5419 2434 7853 22 8305 3104 5436 956 8596 611 3208 8137 4802 2959 6835 9790 1374 16 1928 3933 905 8563 7148 5395 4769 7120 9867 6938 958 902 1635 8282 6853 5974 8667 1135 3544 7781 3724 4634 7479 4471 1938 7625 6909 9912 8309 479 976 9773 4057 5726 1...
output:
599110 3
result:
ok Accepted. 599110 queries used.
Test #21:
score: 70
Accepted
time: 120ms
memory: 5564kb
input:
10000 2047 2226 2047 7482 2047 8002 2047 7874 2471 2047 3951 2047 2047 5793 255 2047 2047 6651 2047 5389 2047 5158 2047 8377 2047 5620 2047 5128 4171 2047 2047 8760 2551 2047 2047 4395 6197 2047 2047 1146 2047 6031 306 2047 9529 2047 2923 2047 2047 8946 590 2047 7820 2047 1096 2047 2047 974 7717 204...
output:
317194 3
result:
ok Accepted. 317194 queries used.
Test #22:
score: 70
Accepted
time: 202ms
memory: 6832kb
input:
10000 9237 9177 5414 5467 9237 68 8026 5985 1926 8283 9237 5640 2996 9237 9237 7417 697 5166 4466 9237 9237 3310 2971 9237 5521 4979 2643 5677 9756 6100 9237 2937 2632 3463 9237 6803 1859 9237 4701 7368 9237 7173 1651 9237 4732 9237 9237 1166 9237 1435 3515 1302 9237 4921 5777 484 8256 7830 9237 960...
output:
481846 3
result:
ok Accepted. 481846 queries used.
Test #23:
score: 70
Accepted
time: 242ms
memory: 6552kb
input:
10000 3351 7696 386 4051 2241 9958 5285 4525 7161 2908 7124 4675 7578 3532 6592 6812 2280 4890 5171 2148 1771 6993 1718 1169 1531 842 1069 3468 1241 7188 5705 5652 4914 677 2363 2546 8117 3848 5023 4984 3187 715 9328 8777 6053 8764 8107 9235 9653 762 3797 183 1973 7599 6175 426 4656 599 6049 1826 84...
output:
563944 3
result:
ok Accepted. 563944 queries used.
Test #24:
score: 70
Accepted
time: 260ms
memory: 6728kb
input:
10000 5331 5033 284 7891 7368 9841 362 6335 1612 1970 1891 4399 7757 7074 9288 3477 7448 9763 3509 1445 6735 2012 789 5030 580 772 8908 720 5536 9474 7121 9522 400 7117 9891 3408 5189 3478 8321 7282 128 8852 3641 4280 7366 5284 3677 1034 43 5886 3769 6199 840 7421 7820 7433 8385 7144 6847 6525 7776 ...
output:
595686 3
result:
ok Accepted. 595686 queries used.
Test #25:
score: 70
Accepted
time: 271ms
memory: 5804kb
input:
10000 7095 4156 8385 4062 1344 1135 4986 3337 7854 7371 2851 9326 1519 5574 6022 842 5234 5680 3231 6393 8582 6669 9168 404 9598 4201 2790 4058 1129 1470 540 5692 7671 8007 1822 1877 921 2656 3941 8775 1467 8859 6488 2326 3813 1878 703 3013 1872 8016 6217 7984 6859 9824 4065 8161 3345 7351 9343 9598...
output:
593336 3
result:
ok Accepted. 593336 queries used.
Test #26:
score: 69.6696
Acceptable Answer
time: 280ms
memory: 6052kb
input:
10000 1906 314 2209 9607 2206 7685 3933 8258 4148 3413 8700 8871 4580 2652 7397 3010 7825 5056 3871 6734 5057 2493 3016 9787 3449 4885 7675 6428 2320 7581 7723 6221 8581 9144 4759 6718 5802 8870 3147 2574 8323 4019 8943 6850 2684 7191 2440 7808 6172 7073 6837 1918 9987 4710 7624 7869 4462 6766 2170 ...
output:
601652 3
result:
points 0.99528 601652 queries used.
Test #27:
score: 70
Accepted
time: 278ms
memory: 6072kb
input:
10000 7603 9574 7601 3270 4487 2470 6976 6163 6714 4553 5829 3006 6102 5259 3028 9549 4948 7712 9726 3157 3221 2634 2222 9435 349 3408 4856 3450 7854 4007 9287 7719 2525 4187 191 5404 1102 8843 9984 7351 4654 1723 90 7437 3472 2121 7768 2935 4977 3484 9853 3895 9772 6586 1853 2880 4813 7094 1639 324...
output:
596496 3
result:
ok Accepted. 596496 queries used.
Test #28:
score: 70
Accepted
time: 274ms
memory: 6032kb
input:
10000 1835 2487 8377 9298 2860 3875 8630 8567 9025 9375 1502 1508 6252 638 68 5585 7400 1125 3175 4043 4225 247 966 3720 8674 673 131 5792 6985 6172 9412 8865 1800 4747 9784 5879 3795 6471 1123 2782 9260 4556 2933 8998 5062 1334 426 8045 2676 4099 2092 2399 4948 6920 5387 8936 211 158 4343 9684 9754...
output:
598294 3
result:
ok Accepted. 598294 queries used.
Test #29:
score: 70
Accepted
time: 121ms
memory: 5560kb
input:
10000 5585 3993 5585 5956 3343 5585 5585 855 5585 6625 5585 8583 5585 4297 5585 7919 5585 284 5585 7150 6979 5585 5585 4458 5585 3606 4838 5585 5576 5585 5585 5077 5585 9525 4975 5585 55 5585 9770 5585 2345 5585 5585 7604 4334 5585 5585 5265 4531 5585 7157 5585 5585 5260 7220 5585 5585 2971 2696 558...
output:
317194 3
result:
ok Accepted. 317194 queries used.
Test #30:
score: 70
Accepted
time: 198ms
memory: 6052kb
input:
10000 7957 6247 9090 5228 5228 2457 5228 2527 6531 9891 1142 5228 6605 5228 1113 5228 7759 8092 3920 5228 5228 1715 5228 4067 5228 7590 2 5228 5228 4780 7683 3450 5228 9327 4805 837 1772 5228 1239 5228 6284 5228 4508 654 8526 5228 1916 7507 5636 5228 1976 282 5228 587 5228 4395 5228 3243 8093 2249 5...
output:
481500 3
result:
ok Accepted. 481500 queries used.
Test #31:
score: 70
Accepted
time: 241ms
memory: 6628kb
input:
10000 9333 69 806 7387 9421 3887 9078 2251 5426 2817 5258 9188 9967 142 430 5752 7860 6903 9925 2527 6873 5691 7536 5960 9386 7136 984 6433 471 5660 6717 1558 8259 3664 8029 1082 6215 918 2173 9388 5670 8237 2073 7710 7244 8127 3089 9644 9722 8829 3299 2559 4495 6213 614 951 737 7768 6120 415 9905 1...
output:
562872 3
result:
ok Accepted. 562872 queries used.
Test #32:
score: 70
Accepted
time: 268ms
memory: 5960kb
input:
10000 5866 7218 2901 5763 1813 8824 3842 7952 1870 8432 7725 9529 9330 2797 8361 465 6858 808 2572 3054 7941 950 4413 1268 5525 2677 4530 3212 3200 848 2682 2888 5400 572 3127 2295 8235 9544 6784 6746 5739 3007 450 4041 5376 7260 3432 9460 6104 3744 7389 3863 8242 5424 7927 2074 6469 7737 5625 4261 ...
output:
594558 3
result:
ok Accepted. 594558 queries used.