QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#800808#9843. Integer GameGSYL#AC ✓211ms3848kbC++141.7kb2024-12-06 15:50:052024-12-06 15:50:05

Judging History

你现在查看的是最新测评结果

  • [2024-12-06 15:50:05]
  • 评测
  • 测评结果:AC
  • 用时:211ms
  • 内存:3848kb
  • [2024-12-06 15:50:05]
  • 提交

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,我给组数据试试?

詳細信息

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