QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#800808 | #9843. Integer Game | GSYL# | AC ✓ | 211ms | 3848kb | C++14 | 1.7kb | 2024-12-06 15:50:05 | 2024-12-06 15:50:05 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int mem[1000][1000][100];
int getsg2(int l,int r,int x){
if(mem[l][r][x] != -1)return mem[l][r][x];
if(r<l)return 0;
set<int> s;
for(int i=r;(i)*x>=r ;i--){
s.insert(getsg2(l,i-1,x));
}
int v = 0;
while(s.count(v))v++;
return mem[l][r][x] = v;
}
int getsg(int l,int r,int x){
// cerr<<l<<' '<<r<<' '<<x<<endl;
while(r%x == 1 && (r-1)/x>=l)r = (r-1)/x-1;
if(r<l)return 0;
// cerr<<r<<endl;
if(r<=x*l)return r-l+1;
// cout<<' '<<l<<' '<<r<<' '<<x<<endl;
return r-l-((r+x-1)/x-l)+1;
}
void solve(){
int n,x;
cin>>n>>x;
int sg = 0;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
sg ^= getsg(l,r,x);
}
if(sg){
cout<<"First"<<endl;
}
else {
cout<<"Second"<<endl;
}
}
signed main(){
// cout<<"Here"<<endl;
// memset(mem, -1,sizeof(mem));
// for(int x = 2;x<100;x++)
// for(int l=1;l<1000;l++)
// for(int r=l+1;r<1000;r++){
// int sg = getsg(l,r,x);
// if(sg != getsg2(l,r,x))
// cout<<l<<' '<<r<<' '<<x<<' '<<getsg2(l,r,x)<<' '<<sg<<endl;
// }
int T;
cin>>T;
while (T--)
{
solve();
}
}
/**
*
4
1 3
1 6
4 100
1 10
2 16
1 7
12 13
3 5
1 8
20 20
13 18
3 2
1 10
2 9
3 4
*
*/
/*
0 0
1 0
2 0
3 0
4 0
5 1
6 2
7 3
8 4
9 5
10 6
11 7
12 8
13 0
14 9
15 10
16 1
17 11
18 12
19 2
20 13
21 14
22 3
23 15
24 16
25 4
26 17
27 18
28 5
29 19
30 20
31 6
32 21
33 22
34 7
35 23
36 24
37 8
38 25
39 26
40 0
41 27
42 28
43 9
44 29
45 30
46 10
47 31
48 32
49 1
*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
4 1 3 1 6 4 100 1 10 2 16 1 7 12 13 3 5 1 8 20 20 13 18 3 2 1 10 2 9 3 4
output:
First Second Second First
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
10 1 45 7214721 324662446 1 4 377416 796130 1 142 6730208 955689537 1 199 680824 895941 1 18 35525862 639465517 1 107 1202052 128619565 1 111 773473 780974 1 32 15249681 487989793 1 158 1232652 194759017 1 23 197942 288268
output:
Second First Second First Second Second First Second Second First
result:
ok 10 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10 11 328 759332 882176 148440 877822 859023 953636 953358 975541 807372 810608 141920 391411 728570 962956 452439 648941 880048 953562 212851 647845 718005 866369 9 2069 1 334044 432918 841149 455570 838897 414239 740868 73601 957565 37263 219021 51433 864487 515433 641190 603864 617645 8 1679 9049...
output:
First Second First First First First Second Second Second First
result:
ok 10 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
100 1 6532 368627 1492830 1 3244 180033 584027053 1 8064 54394 438633217 1 7852 9815491 9878368 1 1742 65714 114473789 1 8814 62363 549667483 1 6037 7514304 7988812 1 3801 8838977 8926601 1 5859 121432 711470089 1 5793 51766 299880439 1 7621 4161178 4425350 1 1754 206134 361559037 1 3688 506432 6986...
output:
First Second Second First Second Second First First Second Second First Second First First Second Second Second Second Second Second First Second First Second First Second Second Second First First First Second First First First First First Second First Second First Second Second First Second First ...
result:
ok 100 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
100 24 25 8171604 8783599 4774417 9456940 9633578 9874450 8516368 9091016 3403923 8685144 2339992 2700436 4769418 9930307 9519374 9906384 107386 9928074 7143431 7724637 8031940 8757025 8988365 9071637 7572797 9209695 9816032 9873939 5538349 6720948 6259570 7052889 562512 6807883 6394986 6551525 8989...
output:
First Second First Second Second Second Second First Second First Second Second First Second Second First Second Second First Second First Second First First First Second Second First First First Second First First First First First First First First First Second Second First Second First Second Fir...
result:
ok 100 lines
Test #6:
score: 0
Accepted
time: 211ms
memory: 3556kb
input:
200000 1 11151 218584062 769621688 1 28414 978824397 999879171 1 90879 2546 231377935 1 21160 249656496 693413744 1 34332 788863536 901667460 1 72452 970301467 972379872 1 62997 15158 954908527 1 29600 182116494 314864401 1 68159 355461063 485568359 1 32456 17622 571939633 1 79160 59490043 683502391...
output:
First First Second First First First Second First First Second First Second Second Second First Second Second Second First First Second First First First First Second First First First Second Second Second Second Second Second Second First First Second First Second Second Second Second Second Second...
result:
ok 200000 lines
Test #7:
score: 0
Accepted
time: 95ms
memory: 3556kb
input:
10 19941 4697 635193474 957715929 465635702 804696741 591162864 608604763 879457309 956212295 831311476 929083016 181987114 733754987 908355819 928179039 156991686 931013583 688834408 790067350 196002188 400175238 105437106 286646840 789619470 847112691 882603971 981853406 894405200 937027692 712184...
output:
First First First First Second First Second First Second Second
result:
ok 10 lines
Test #8:
score: 0
Accepted
time: 100ms
memory: 3616kb
input:
1000 192 7708332 18871536 339166609 130246440 192708301 309805422 978958165 82526632 107916649 774173020 809374861 450530818 501041581 126306591 146458309 336764188 678333217 174776440 901874845 281310415 901874845 403012014 431666593 876471963 948124837 150512900 362291605 365615829 955833169 40917...
output:
First Second Second First Second Second Second Second Second Second First First Second First Second Second First Second Second First Second First First First First Second First First First First First First First First First Second Second First First First First First Second Second Second Second Fir...
result:
ok 1000 lines
Test #9:
score: 0
Accepted
time: 99ms
memory: 3564kb
input:
100 2032 719837 94522238 656491345 96296538 305210889 192921382 352000294 5464442 18715763 793450509 891158207 267447607 709039446 163526706 212351916 65834365 530519870 81957749 128130987 255345219 485170139 113039168 627697865 14544525 932188916 335445852 629137539 382710470 873162282 194775420 49...
output:
First First First Second Second Second Second Second Second First Second Second Second First Second First First Second First First Second Second Second Second First First Second Second Second First Second Second Second Second Second Second First First Second First First Second Second Second First Se...
result:
ok 100 lines
Test #10:
score: 0
Accepted
time: 97ms
memory: 3588kb
input:
1 200000 194 433249323 519407647 207012171 426509583 252808520 619975307 201424805 376863237 601396408 778875275 463396113 589228053 124923685 198007459 93996810 99570307 43336901 302292353 661332116 670383297 335492245 418515231 369129843 593513901 127054188 568058191 83641852 966580363 149389710 2...
output:
First
result:
ok single line: 'First'
Test #11:
score: 0
Accepted
time: 98ms
memory: 3848kb
input:
1 200000 951 325631409 486447913 227257623 384938173 55905094 256497064 76664971 334418200 42706688 714458722 774998837 897302737 433765092 578862289 60898552 929465557 188080902 687905851 416852835 743781856 152633050 346504459 310279922 488001847 266342513 775142983 465619179 591932833 425757395 5...
output:
First
result:
ok single line: 'First'
Test #12:
score: 0
Accepted
time: 102ms
memory: 3632kb
input:
1 200000 2 255821481 330717200 713979422 949781023 369744704 905920045 814952911 975814643 605990046 679618081 104771976 525461081 894802084 951667773 40527031 223910434 270018282 509495956 472498620 600218352 24785721 823266836 417198700 660349561 938937873 971399165 58935950 947224400 941642020 98...
output:
First
result:
ok single line: 'First'
Test #13:
score: 0
Accepted
time: 100ms
memory: 3720kb
input:
1 200000 5 995416719 998485041 908771297 971462780 33758952 836479961 558656411 942734287 240950566 747509340 360315149 640224087 138395287 628710766 959140969 970605527 217343088 734997930 571597316 724100781 995787337 996534841 989212889 992520095 393671839 403991060 885809413 905583176 305179473 ...
output:
First
result:
ok single line: 'First'
Test #14:
score: 0
Accepted
time: 99ms
memory: 3848kb
input:
1 200000 2 793095688 964042388 893563499 922317367 730024959 763916464 1990357 604681571 484009040 675317344 469394403 530746115 41793567 947884251 694338028 864733120 257479702 561877561 608460043 683561552 133700322 645073725 913619871 956264717 493474741 657552957 212285643 790660161 995368643 99...
output:
First
result:
ok single line: 'First'
Test #15:
score: 0
Accepted
time: 95ms
memory: 3560kb
input:
1 200000 87 305623694 503198996 949654443 959846123 146449469 964498906 812046847 945964778 645987528 924642199 716043555 844416577 713308702 837539184 305420898 326812293 184022148 794617823 213579417 768264368 810827535 985368483 458869946 948652693 636473389 971109226 934936651 971210214 80839068...
output:
First
result:
ok single line: 'First'
Test #16:
score: 0
Accepted
time: 107ms
memory: 3636kb
input:
1 200000 2 919791500 953529115 681406916 755667337 117655429 939116601 800198040 885054879 358025807 842252835 65008548 632007831 751514018 928764583 545594115 547546815 189093914 481214098 435882483 972546244 987782583 994866593 741518933 821216030 441528927 665378103 229872689 830879713 576372823 ...
output:
First
result:
ok single line: 'First'
Test #17:
score: 0
Accepted
time: 99ms
memory: 3632kb
input:
1 200000 11 99578226 298630845 1 544097388 781669677 845597712 543901540 671419699 992986326 993836931 320551721 747783893 995107220 997241809 169240756 705364005 286161824 709342105 829948474 948567409 958784200 991136043 313533122 363935435 456071405 752123232 616554664 859433787 644942981 8657411...
output:
Second
result:
ok single line: 'Second'
Test #18:
score: 0
Accepted
time: 102ms
memory: 3552kb
input:
1 200000 2 752033004 876241133 860990993 992771300 477935684 761402994 987235486 995266176 531012096 662159394 429630975 555856383 898505500 900784123 199405112 576163086 881588038 947226449 717068098 828843098 391664481 944885072 648005513 791028077 850841602 909010962 678189678 936373742 335132150...
output:
First
result:
ok single line: 'First'
Test #19:
score: 0
Accepted
time: 99ms
memory: 3528kb
input:
1 200000 93 1 628001362 917081937 941400044 894360194 966811288 502324680 777316624 398023289 933513955 971247423 991430541 570020636 724954896 105455278 471708179 957873588 958243372 881995984 960943965 923567501 990840239 193255588 540268367 698872955 983482328 400840685 667703981 443121488 833843...
output:
Second
result:
ok single line: 'Second'
Test #20:
score: 0
Accepted
time: 99ms
memory: 3556kb
input:
1 200000 7831427 1 873839188 605928001 991518240 716503437 980325107 887424184 982795330 671999860 687511230 542308218 964491233 859753133 965406081 357685119 819639123 298715539 387816097 253760676 738977765 707360676 784307880 408050216 921233920 120635394 724591483 872715055 874304743 229510131 3...
output:
Second
result:
ok single line: 'Second'
Test #21:
score: 0
Accepted
time: 100ms
memory: 3620kb
input:
1 200000 66301700 1 805360997 492460468 566168877 198023426 552856882 72713385 530445011 249616676 381316573 725724309 948090012 93046230 341487226 806314701 844324499 920139780 927951658 269116280 326608284 457289392 615176962 982562321 986378299 423751024 794183208 931957737 972029682 728245486 98...
output:
Second
result:
ok single line: 'Second'
Test #22:
score: 0
Accepted
time: 92ms
memory: 3620kb
input:
1 200000 509082951 1 175487762 531131265 602978675 832983946 856509481 738321966 878774398 343466775 420892139 644338247 671838763 40371036 241277633 200380693 321380303 891141396 956795986 841130469 846624918 766799166 954738776 664211592 792343480 932512669 935568497 926418387 974500012 449487673 ...
output:
Second
result:
ok single line: 'Second'
Test #23:
score: 0
Accepted
time: 48ms
memory: 3820kb
input:
1000 109 1000000000 851925882 878969309 55598903 106098564 55266120 439936122 847310417 951788602 787168177 821998294 884664819 941282000 91909258 397563257 903759037 905037053 418142176 860921485 1584836 613514466 138582640 737403275 365055504 634039901 251673645 929473743 168738078 793336155 44992...
output:
First First Second First Second First Second First Second First Second Second Second First First First Second Second Second Second Second Second Second First Second Second Second First Second First First Second First First Second Second First First First Second First Second First Second First First ...
result:
ok 1000 lines
Test #24:
score: 0
Accepted
time: 50ms
memory: 3848kb
input:
10 10088 1000000000 337078091 664858164 848020992 933959017 868178461 983321779 560537111 738032102 264542992 808509190 197191274 542389161 95284893 466341139 543481162 821493133 801761424 825969314 635765149 982405038 811880582 954671144 871123803 879183954 985958006 989985795 651954195 996501173 4...
output:
First First Second First First Second Second First Second First
result:
ok 10 lines
Test #25:
score: 0
Accepted
time: 99ms
memory: 3588kb
input:
1 200000 1000000000 38973108 44609632 607047864 806496775 562351350 757016996 263381873 929714439 644059730 663172395 531255035 929587067 140845147 939805085 222005891 331743136 775886201 925519992 397269324 590576363 989475688 996148044 339156267 653070811 668387255 678428380 218408201 833278659 27...
output:
First
result:
ok single line: 'First'
Test #26:
score: 0
Accepted
time: 102ms
memory: 3820kb
input:
1000 188 1941 190688416 890195676 196792768 906021743 427411597 636061396 164821004 166880462 644030300 672842886 609709303 925089741 623574584 904467171 917787420 945911699 709871692 986883663 466523994 492339402 322874187 767972304 836541269 866716487 825250793 937845273 774183410 819203767 134289...
output:
First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First First ...
result:
ok 1000 lines
Test #27:
score: 0
Accepted
time: 99ms
memory: 3632kb
input:
1 200000 3385427 641419340 797746741 235044105 882193993 132360225 937830884 657331573 923671885 371406905 694692112 360424134 434429104 759279022 968510443 190835729 654380252 559194926 645893928 697621820 841052693 894749562 933394331 878329732 983539132 89793512 118548407 725949433 967090116 3996...
output:
First
result:
ok single line: 'First'
Test #28:
score: 0
Accepted
time: 98ms
memory: 3620kb
input:
1000 181 345975651 1 575468090 542196379 749229508 155724836 843584412 46081425 848585942 301886722 457141114 246708631 789213817 645159255 873984520 186562899 362467892 705609226 781816612 134001679 973788749 730898152 742051010 351660089 380604480 369172258 910321771 881547236 959582235 661785034 ...
output:
Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second Second...
result:
ok 1000 lines
Test #29:
score: 0
Accepted
time: 99ms
memory: 3776kb
input:
1 200000 9844 1 618914061 80211114 169196108 78515731 217181134 912395801 974268102 591965193 992876334 880291526 952567433 43560193 104231806 546390695 774909159 413529499 541249071 434679717 772358370 32114089 100814749 328746523 749148126 255869106 410730590 707717467 768806157 565617776 91404860...
output:
Second
result:
ok single line: 'Second'
Test #30:
score: 0
Accepted
time: 95ms
memory: 3656kb
input:
100 1947 27 1 378889925 890941565 959712858 545070054 893914430 475731993 782972495 998876508 998922773 819319340 824407602 100347998 650399351 760185478 967724400 25866141 363506890 149089501 173162254 440885231 768726323 365706568 741510671 338782416 907389476 435864260 655867874 500596444 8953801...
output:
Second First First Second First First Second First Second First Second Second Second First Second First Second First First First First Second Second First First First First First First First Second Second First First First Second Second First Second First Second First First Second Second First Secon...
result:
ok 100 lines
Test #31:
score: 0
Accepted
time: 102ms
memory: 3632kb
input:
100 2011 4 1 181167978 327552169 529134247 572451091 726351163 87188811 124947122 651152883 928309484 830721909 912091264 620756314 631157944 701222620 808158080 936564409 958467426 604744265 739207782 663436242 734823505 481922075 901766112 229370686 378549892 197807298 790302783 891156201 93826219...
output:
Second First First Second First First First Second First First Second Second First First First Second First Second First Second First Second Second Second First First First First First First First Second Second First First First Second First Second Second Second Second First First First First First ...
result:
ok 100 lines
Test #32:
score: 0
Accepted
time: 100ms
memory: 3848kb
input:
100 1986 4 628395795 766581783 1 465509846 521974534 859817543 106322575 373563190 984308973 995064753 792287505 851279240 229216032 975790963 516966227 675013489 542407966 710520057 112854164 745645340 831696393 857442479 126173176 839602599 451370791 849267997 268898568 474162465 838436962 9736233...
output:
Second Second First First First Second Second Second Second Second First Second Second Second Second First First First First Second First Second Second First First First Second First First First First Second First First Second Second First First Second Second Second Second Second First First First F...
result:
ok 100 lines
Test #33:
score: 0
Accepted
time: 100ms
memory: 3560kb
input:
100 2026 35 1 506313293 754636051 844272979 424181044 438102035 915881481 987543337 286795835 897175333 189593241 955092688 563745650 686698789 348829990 960582414 881911290 916071371 884852524 896185014 535699271 550902053 975572920 997551158 172243872 911098750 238467051 590373421 579744416 777968...
output:
Second First Second Second First Second First Second First First First First First Second Second Second First First First Second Second Second First First Second Second Second Second First Second Second Second First Second Second First First Second Second Second First Second First Second Second Firs...
result:
ok 100 lines
Extra Test:
score: 0
Extra Test Passed