QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #87924 | #5029. 在路上 | CharlieVinnie | 22 | 1522ms | 28548kb | C++14 | 1.7kb | 2023-03-14 20:34:36 | 2023-03-14 20:34:38 |
Judging History
answer
#include "path.h"
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; using ll = long long;
const int N=3e4+5;
mt19937 rng(190345); int n,siz[N],ban[N],Ans;
bitset<N> GetBig(int u){
int v=0,cnt=0; For(i,1,n) if(!ban[i]&&i!=u){
if(ask(u,v,i)!=u){
if(cnt==0) v=i;; cnt+=siz[i];
}
else{
if(cnt>siz[i]) cnt-=siz[i]; else if(cnt==siz[i]) cnt=v=0; else cnt=siz[i]-cnt,v=i;
}
}
if(v==0) return Ans=u,bitset<N>();
bitset<N> res; res.set(v);
For(i,1,n) if(!ban[i]&&i!=u&&i!=v&&ask(u,v,i)!=u) res.set(i);
if(res.count()<=n/2u) Ans=u;
return res;
}
int Rand(const bitset<N>& bs){
assert(bs.count());
vector<int> lis; For(i,1,n) if(bs.test(i)) lis.push_back(i);
int sz=lis.size(); return lis[uniform_int_distribution<int>(0,sz-1)(rng)];
}
int centroid(int id,int _n,int){
n=_n; Ans=0; if(id==1) return ask(1,2,3);
int u=uniform_int_distribution<int>(1,n)(rng);
For(i,1,n) siz[i]=1,ban[i]=0;
bitset<N> U=GetBig(u); if(Ans) return Ans;
int v=Rand(U); bitset<N> V=GetBig(v); if(Ans) return Ans;
auto S=U&V;
//~ For(i,1,n) if(!S.test(i)) ban[i]=1;
//~ siz[u]=n-U.count()+1,siz[v]=n-V.count()+1;
while(true){
int x=Rand(S),z=0;
For(i,1,n) if(S.test(i)&&ask(u,i,x)==i&&ask(v,i,x)==i) { z=i; break; }
assert(z);
bitset<N> Z=GetBig(z); if(Ans) return Ans;
if(Z.test(u)) v=z,V=Z;
else u=z,U=Z;
S=U&V;
//~ For(i,1,n) if(!S.test(i)) ban[i]=1;
//~ siz[u]=n-U.count()+1,siz[v]=n-V.count()+1;
}
}
#ifndef ONLINE_JUDGE
#include "grader.cpp"
#endif
详细
Subtask #1:
score: 2
Accepted
Test #1:
score: 2
Accepted
time: 3ms
memory: 9616kb
input:
1 100 100 3 1 2 3 1 2 3 3 1 3 1 2 3 1 2 3 3 1 3 1 2 3 3 1 3 1 2 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 1 2 3 1 2 3 3 1 3 3 1 3 1 2 3 3 1 3 3 1 3 1 2 3 3 1 3 3 1 3 1 2 3 3 1 3 3 1 3 3 1 3 1 2 3 1 2 3 3 1 3 3 1 3 1 2 3 1 2 3 1 2 3 1 2 3 3 1 3 3 1 3 3 1 3 1 2 3 1 2 3 1 2 3 3 1 3 3 1 3 3 1 3 ...
result:
ok correct
Subtask #2:
score: 8
Accepted
Test #2:
score: 8
Accepted
time: 5ms
memory: 11952kb
input:
2 10 10000000 999 60 112 98 509 586 175 588 875 861 516 920 370 781 249 999 649 292 308 934 949 437 92 506 752 547 866 869 510 984 228 104 612 202 630 360 809 56 107 566 448 940 726 146 299 941 50 319 794 670 603 365 492 728 872 829 942 451 632 373 106 909 25 306 995 735 99 568 673 75 573 383 407 56...
result:
ok correct
Test #3:
score: 0
Accepted
time: 6ms
memory: 3932kb
input:
2 10 10000000 999 60 112 98 509 586 175 588 875 861 516 920 370 781 249 999 649 292 308 934 949 437 92 506 752 547 866 869 510 984 228 104 612 202 630 360 809 56 107 566 448 940 726 146 299 941 50 319 794 670 603 365 492 728 872 829 942 451 632 373 106 909 25 306 995 735 99 568 673 75 573 383 407 56...
result:
ok correct
Test #4:
score: 0
Accepted
time: 10ms
memory: 3792kb
input:
2 10 10000000 999 60 112 959 68 586 835 91 836 634 516 272 912 781 249 655 11 466 103 934 816 904 92 576 83 687 435 871 510 758 519 842 882 339 221 2 917 5 605 477 448 323 723 744 494 941 50 668 751 670 336 365 95 877 159 829 957 451 632 591 616 909 83 452 607 735 99 22 570 755 354 172 711 742 870 3...
result:
ok correct
Test #5:
score: 0
Accepted
time: 15ms
memory: 3720kb
input:
2 10 10000000 999 373 769 355 568 586 175 588 836 203 901 272 948 781 80 655 11 292 103 934 595 904 188 865 989 698 493 871 510 893 228 842 882 339 630 2 550 829 107 477 636 385 726 146 299 764 670 668 381 631 336 365 95 974 872 829 733 678 669 373 571 183 752 452 607 735 179 22 673 755 354 383 711 ...
result:
ok correct
Test #6:
score: 0
Accepted
time: 7ms
memory: 3748kb
input:
2 10 10000000 999 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 68...
result:
ok correct
Test #7:
score: 0
Accepted
time: 4ms
memory: 3804kb
input:
2 10 10000000 999 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 68...
result:
ok correct
Test #8:
score: 0
Accepted
time: 146ms
memory: 3788kb
input:
2 10 10000000 999 158 826 595 867 47 385 664 154 455 857 622 561 166 780 801 763 33 310 605 36 199 718 762 911 419 109 947 369 861 841 902 657 172 175 461 814 473 43 90 875 62 238 669 791 68 435 405 663 756 255 628 798 745 878 257 773 652 662 832 735 75 363 129 359 230 351 667 873 602 783 988 253 58...
result:
ok correct
Test #9:
score: 0
Accepted
time: 99ms
memory: 3792kb
input:
2 10 10000000 999 279 772 39 665 622 173 514 309 407 623 288 342 100 529 202 417 132 611 186 430 634 796 454 842 92 53 977 712 975 158 654 66 822 452 6 333 596 593 91 119 242 503 190 82 97 575 663 574 75 598 299 334 31 147 382 988 702 11 801 338 164 696 573 182 899 948 507 168 331 939 442 137 581 52...
result:
ok correct
Test #10:
score: 0
Accepted
time: 10ms
memory: 3800kb
input:
2 10 10000000 999 60 208 208 208 208 175 208 875 861 208 208 370 208 208 208 208 292 208 208 949 208 208 208 752 547 208 869 510 208 208 208 612 208 208 360 809 208 107 208 448 208 208 208 208 941 208 319 794 208 603 208 208 208 208 208 208 451 208 373 106 208 25 306 208 735 99 208 673 208 573 383 2...
result:
ok correct
Test #11:
score: 0
Accepted
time: 10ms
memory: 3728kb
input:
2 10 10000000 999 60 208 208 208 208 175 208 875 861 208 208 370 208 208 208 208 292 208 208 949 208 208 208 752 547 208 869 510 208 208 208 612 208 208 360 809 208 107 208 448 208 208 208 208 941 208 319 794 208 603 208 208 208 208 208 208 451 208 373 106 208 25 306 208 735 99 208 673 208 573 383 2...
result:
ok correct
Test #12:
score: 0
Accepted
time: 123ms
memory: 3820kb
input:
2 10 10000000 999 198 236 761 86 644 189 7 741 274 656 547 36 825 827 740 333 896 832 575 37 359 456 833 590 427 837 100 60 424 237 208 742 266 543 941 906 422 423 953 787 397 337 215 469 979 51 404 546 603 168 849 472 737 135 500 701 608 696 764 695 64 590 851 194 89 278 864 314 529 165 448 414 471...
result:
ok correct
Test #13:
score: 0
Accepted
time: 118ms
memory: 3824kb
input:
2 10 10000000 999 198 236 761 86 644 189 7 741 274 656 547 36 825 827 740 333 896 832 575 37 359 456 833 590 427 837 100 60 424 237 208 742 266 543 941 906 422 423 953 787 397 337 215 469 979 51 404 546 603 168 849 472 737 135 500 701 608 696 764 695 64 590 851 194 89 278 864 314 529 165 448 414 471...
result:
ok correct
Test #14:
score: 0
Accepted
time: 12ms
memory: 3824kb
input:
2 10 10000000 999 60 112 98 509 586 175 588 875 861 516 920 370 781 249 999 649 292 308 934 949 437 92 506 752 547 866 869 510 984 228 338 612 202 630 360 809 56 107 566 448 940 726 146 299 941 50 319 794 670 603 365 492 728 872 829 942 451 632 373 106 909 25 306 995 735 99 568 673 75 573 383 407 56...
result:
ok correct
Test #15:
score: 0
Accepted
time: 13ms
memory: 3936kb
input:
2 10 10000000 999 60 112 98 509 586 175 588 875 861 516 920 370 781 249 999 649 292 308 934 949 437 92 506 752 547 866 869 510 984 228 991 612 202 630 360 809 56 107 566 448 940 726 146 299 941 50 319 794 670 603 365 492 728 872 829 942 451 632 373 106 909 25 306 995 735 99 568 673 75 573 383 407 56...
result:
ok correct
Test #16:
score: 0
Accepted
time: 33ms
memory: 3828kb
input:
2 10 10000000 999 60 112 125 509 291 175 588 875 861 516 920 370 781 618 999 649 292 45 934 949 437 92 506 752 547 866 869 510 208 991 338 612 208 630 360 809 56 107 737 448 940 726 208 291 941 50 319 794 670 603 365 618 291 159 829 942 451 632 373 106 847 25 306 125 735 99 568 673 642 573 383 338 5...
result:
ok correct
Test #17:
score: 0
Accepted
time: 19ms
memory: 3764kb
input:
2 10 10000000 999 60 112 338 509 847 175 588 875 861 516 920 370 781 249 999 649 292 618 934 949 437 92 506 752 547 866 869 510 125 291 515 612 737 630 360 809 56 107 208 448 940 726 515 338 941 50 319 794 670 603 365 125 125 515 829 942 451 632 373 106 902 25 306 515 735 99 568 673 907 573 383 291 ...
result:
ok correct
Test #18:
score: 0
Accepted
time: 8ms
memory: 3836kb
input:
2 10 10000000 999 60 736 736 736 736 175 736 875 861 736 736 370 736 736 736 736 292 736 736 949 736 736 736 752 547 736 869 510 736 736 736 612 736 736 360 809 736 107 736 448 736 736 736 736 941 736 319 794 736 603 736 736 736 736 736 736 451 736 373 106 736 25 306 736 735 99 736 673 736 573 383 7...
result:
ok correct
Test #19:
score: 0
Accepted
time: 8ms
memory: 3756kb
input:
2 10 10000000 999 60 736 736 736 736 175 736 875 861 736 736 370 736 736 736 736 292 736 736 949 736 736 736 752 547 736 869 510 736 736 736 612 736 736 360 809 736 107 736 448 736 736 736 736 941 736 319 794 736 603 736 736 736 736 736 736 451 736 373 106 736 25 306 736 735 99 736 673 736 573 383 7...
result:
ok correct
Test #20:
score: 0
Accepted
time: 17ms
memory: 3792kb
input:
2 10 10000000 999 60 825 542 207 182 175 71 875 861 275 642 370 725 600 184 242 292 978 56 949 189 839 896 752 547 479 869 510 328 592 288 612 373 975 360 809 317 107 642 448 822 742 200 947 941 614 319 794 580 603 473 760 89 872 342 160 451 326 373 106 488 25 306 39 735 99 533 673 94 573 383 473 56...
result:
ok correct
Test #21:
score: 0
Accepted
time: 28ms
memory: 3808kb
input:
2 10 10000000 999 60 702 344 961 410 175 657 875 861 502 500 370 194 97 850 849 292 681 289 949 574 375 233 752 547 708 869 510 457 80 683 612 752 653 360 809 64 107 127 448 941 704 685 448 941 535 319 794 945 603 901 318 460 388 672 460 451 946 373 106 10 25 306 318 735 99 502 673 304 573 383 227 5...
result:
ok correct
Subtask #3:
score: 12
Accepted
Test #22:
score: 12
Accepted
time: 74ms
memory: 4064kb
input:
3 100 10000000 999 328 852 537 953 554 506 483 192 443 912 989 346 935 232 652 528 261 899 131 531 81 686 815 543 991 810 576 639 670 572 604 842 546 322 916 97 510 160 238 696 882 214 212 194 102 964 719 255 416 260 687 148 225 664 105 100 913 600 921 203 571 406 752 189 929 716 523 809 666 589 235...
result:
ok correct
Test #23:
score: 0
Accepted
time: 82ms
memory: 4168kb
input:
3 100 10000000 999 603 168 694 35 890 839 431 506 172 225 322 14 231 221 387 802 768 786 858 954 214 929 553 795 917 554 453 983 112 196 5 428 421 149 960 294 875 380 900 914 135 141 398 480 716 377 693 832 582 629 59 975 998 513 351 193 293 328 677 96 338 39 569 236 243 849 254 418 877 413 7 675 69...
result:
ok correct
Test #24:
score: 0
Accepted
time: 70ms
memory: 4280kb
input:
3 100 10000000 999 232 191 603 626 730 411 104 65 39 494 691 185 208 192 567 818 210 162 385 511 733 860 72 765 262 635 485 516 768 426 641 477 334 92 555 520 173 296 621 80 312 695 168 760 182 556 716 457 123 718 147 474 246 9 221 369 266 912 365 247 575 86 120 584 755 525 527 276 623 323 572 550 1...
result:
ok correct
Test #25:
score: 0
Accepted
time: 77ms
memory: 4176kb
input:
3 100 10000000 999 37 333 429 430 950 395 199 67 394 239 625 725 586 176 839 401 226 14 898 931 541 738 560 638 302 457 846 468 193 423 215 692 746 262 722 43 869 984 510 181 977 809 805 327 22 444 208 768 47 372 946 20 958 863 147 409 224 95 466 694 837 167 195 949 778 24 126 953 852 480 730 365 13...
result:
ok correct
Test #26:
score: 0
Accepted
time: 73ms
memory: 4192kb
input:
3 100 10000000 999 289 402 626 749 480 763 773 565 829 569 200 303 980 734 514 539 440 769 674 130 102 117 798 994 919 493 149 456 109 121 587 835 386 851 657 268 67 382 612 792 541 883 742 436 403 968 872 60 983 260 76 550 571 158 635 428 877 807 681 604 513 598 459 218 173 599 683 308 727 221 733 ...
result:
ok correct
Subtask #4:
score: 0
Wrong Answer
Test #27:
score: 17
Accepted
time: 80ms
memory: 4208kb
input:
4 100 10000000 999 710 227 715 954 623 585 538 236 363 913 540 3 897 998 726 919 976 843 796 69 415 705 647 707 201 696 993 545 325 375 47 260 490 385 828 162 29 278 867 593 395 219 178 518 999 685 307 772 224 187 557 89 575 524 1 157 230 341 708 978 473 995 15 179 743 416 263 640 4 851 520 719 679 ...
result:
ok correct
Test #28:
score: 0
Accepted
time: 73ms
memory: 4188kb
input:
4 100 10000000 999 714 793 831 566 274 202 861 272 583 533 805 725 138 636 832 242 737 219 191 168 939 364 439 770 290 84 581 419 991 431 892 387 487 753 368 627 900 476 934 316 854 802 898 48 741 182 950 684 121 881 996 120 917 311 386 63 377 300 734 333 789 257 797 134 668 490 649 843 795 198 462 ...
result:
ok correct
Test #29:
score: 0
Accepted
time: 170ms
memory: 5840kb
input:
4 100 10000000 999 118 434 443 62 975 789 284 936 885 652 937 50 912 733 854 532 772 709 407 312 535 589 419 247 190 474 469 905 165 889 13 159 189 746 837 603 181 335 880 513 496 897 887 442 498 656 838 342 522 93 771 816 178 541 788 215 586 794 267 297 938 853 244 255 640 654 101 470 621 232 162 8...
result:
ok correct
Test #30:
score: 0
Accepted
time: 160ms
memory: 4104kb
input:
4 100 10000000 999 418 71 357 515 696 936 943 436 645 53 344 262 706 201 896 877 732 738 433 684 891 641 264 615 32 659 990 529 219 165 81 420 22 61 35 704 233 339 201 42 816 126 522 561 960 673 452 720 99 328 222 423 804 226 266 652 291 939 981 503 209 275 653 525 812 886 693 343 881 353 218 227 28...
result:
ok correct
Test #31:
score: 0
Accepted
time: 87ms
memory: 4112kb
input:
4 100 10000000 999 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 3...
result:
ok correct
Test #32:
score: 0
Accepted
time: 54ms
memory: 4064kb
input:
4 100 10000000 999 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 1...
result:
ok correct
Test #33:
score: -17
Wrong Answer
time: 245ms
memory: 3940kb
input:
4 100 10000000 999 962 472 490 254 571 779 648 83 213 290 889 914 69 311 578 495 455 361 519 832 796 230 588 172 320 357 123 142 703 590 9 669 728 63 829 749 585 11 131 478 744 657 605 614 942 267 108 587 852 148 491 757 256 450 739 16 174 556 94 810 582 426 562 482 629 699 529 152 278 176 696 443 1...
result:
wrong answer too many queries
Subtask #5:
score: 0
Runtime Error
Test #47:
score: 0
Runtime Error
input:
5 100 25000000 49999 3753 28650 36024 8322 47241 9061 43764 6338 45160 16765 40294 43358 37214 37535 38561 1997 7478 9543 11661 1953 7391 41171 43559 9981 24218 13155 22152 45216 30123 1843 20703 23601 42707 6449 40356 3761 32284 34584 32674 44391 41031 324 14845 6935 37071 38330 48041 1824 41182 46...
result:
Subtask #6:
score: 0
Wrong Answer
Test #52:
score: 12
Accepted
time: 1019ms
memory: 17708kb
input:
6 100 40000000 9999 3929 7460 4617 7377 498 7572 4628 3661 2404 9179 755 4076 8531 6581 1929 9419 1498 4402 6412 712 4918 2628 798 6283 9427 9775 1472 5554 2146 9972 5228 5459 8417 6778 3121 7649 1031 7691 6270 2238 4885 6121 2099 3435 4615 9962 6384 8809 9169 4553 66 1939 8589 2029 4897 7334 2867 8...
result:
ok correct
Test #53:
score: 0
Accepted
time: 1026ms
memory: 12124kb
input:
6 100 40000000 9999 3234 8857 2432 8719 9275 4386 9289 1618 6926 1459 2895 7304 8659 2496 301 2247 4005 3433 3746 8039 343 7038 7370 44 558 8034 5438 2934 1311 5743 2668 8493 8081 2248 968 4448 1148 6299 4078 8794 1317 5172 9487 6794 1184 1501 4564 7710 7754 7183 381 5002 2115 9361 7406 9929 3890 53...
result:
ok correct
Test #54:
score: -12
Wrong Answer
time: 1092ms
memory: 10168kb
input:
6 100 40000000 9999 8081 4107 1424 1165 6434 2326 5528 8697 6543 826 4274 210 1640 1277 1540 9677 5665 9386 1542 7906 1765 3085 7702 9076 7876 4395 1692 1342 6072 1247 517 4487 4463 8189 4891 4829 4775 3290 6530 9093 4119 5963 6310 7673 1873 4548 5578 9671 1418 1963 7601 9038 5798 1118 5482 6226 6 7...
result:
wrong answer too many queries
Subtask #7:
score: 0
Wrong Answer
Test #72:
score: 0
Wrong Answer
time: 1226ms
memory: 19184kb
input:
7 50 40000000 29999 12447 18709 13054 17585 8337 14953 7985 1930 24383 1787 2543 26860 12198 2842 14256 8665 17034 6429 14773 8646 27093 6362 29357 18001 10667 8445 6671 21435 27163 14604 19875 745 20772 6696 16391 15560 16789 10983 6199 23133 13 13688 14547 8390 4398 21653 14460 690 24385 5358 2213...
result:
wrong answer too many queries
Subtask #8:
score: 0
Wrong Answer
Test #92:
score: 0
Wrong Answer
time: 1522ms
memory: 28548kb
input:
8 100 50000000 29999 8375 16777 16700 20953 11899 14682 20874 25860 28858 23241 5089 8044 25448 17746 5605 3087 9145 20179 1080 22944 27383 8384 19943 15371 27572 7882 23028 10474 18744 20202 15687 17001 7543 18709 23165 15713 17032 29011 22353 17455 26045 3484 20330 15159 21274 382 23927 20114 6303...
result:
wrong answer too many queries