QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471873#5024. 【模板】双端队列wsc2008100 ✓73ms4328kbC++141.5kb2024-07-11 10:41:412024-07-11 10:41:41

Judging History

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

  • [2024-07-11 10:41:41]
  • 评测
  • 测评结果:100
  • 用时:73ms
  • 内存:4328kb
  • [2024-07-11 10:41:41]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=5e4+9;
ll T,n,a[N];
bool chk(ll l,ll r){
    ll s=0;
    rep(i,l,r)s+=a[i];
    if(s%4)return 0;
    while(l<=r&&a[l]==a[r])l++,r--;
    if(l>r)return 1;
    rep(i,l,r){
        if((i-l+1)&1){
            if(a[i]!=a[i+1])return 0;
        }
    }
    return 1;
}
void solve(){
    n=read();
    rep(i,1,n)a[i]=read();
    per(i,30,0){
        ll cnt=0;
        rep(j,1,n){
            if((a[j]>>i)&1)cnt++;
        }
        if(cnt&1){
            rep(j,1,n)a[j]=(a[j]>>i)&1;
            break;
        }
        if(!i)return puts("Draw"),void();
    }
    if(!(n&1))return puts("First"),void(); 
    if(!a[1]&&!a[n])return puts("Second"),void();
    if(chk(2,n)||chk(1,n-1))return puts("First"),void();
    puts("Second");
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    T=read();
    while(T--)solve();
    cerr<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 0ms
memory: 3844kb

input:

40
15
1042186166 1065050038 1052442342 117744385 1044381358 996146407 947617159 1031691934 27328777 130294601 1065311743 1065082111 12845136 941620871 1042177446
15
1068465534 15766217 69219008 95461385 1048542590 1051709438 1048575351 1072652151 978275647 1044381687 999247358 1062194999 1054829887 ...

output:

Second
Second
Second
First
First
Second
Second
Draw
Draw
Draw
Draw
Second
Second
Second
Second
First
First
Draw
Second
Second
Second
Draw
Second
Draw
Draw
First
Second
Second
Draw
Second
First
First
Second
Second
First
First
Second
First
First
Draw

result:

ok 40 tokens

Subtask #2:

score: 20
Accepted

Test #2:

score: 20
Accepted
time: 0ms
memory: 3728kb

input:

40
987
1073733087 9437225 570431533 1031755263 1031755251 579873284 571521061 536872960 546353705 43000364 535780827 1065313790 536834043 41953824 503270871 1040175099 8426021 537960961 1054732 545292837 34648585 34603052 546314244 537965060 9439748 41953292 43037189 9447949 536864767 1073698294 503...

output:

Second
Second
First
Second
First
Second
Second
First
Second
First
Draw
First
Second
First
First
Second
Second
Second
Draw
Draw
Draw
Draw
First
Second
Second
Second
Second
First
Second
Second
Draw
Second
First
Second
First
Draw
Second
First
First
First

result:

ok 40 tokens

Test #3:

score: 0
Accepted
time: 2ms
memory: 3904kb

input:

40
985
1051584087 161093905 991143886 498485632 221004168 788260831 916059871 274356401 213536945 95177001 98458032 869773278 787854966 1051043535 603582199 3672200 216942729 975171167 93067289 603832174 292948248 602275551 354556312 4589841 22567337 428083233 89540913 589692543 361906352 77353112 9...

output:

Second
First
Draw
Second
First
Second
Draw
First
First
Second
First
Draw
First
First
Draw
Second
First
Second
Second
Draw
First
First
First
Second
Second
Second
Draw
First
Second
Second
First
Second
First
Second
First
First
Second
First
First
First

result:

ok 40 tokens

Subtask #3:

score: 25
Accepted

Test #4:

score: 25
Accepted
time: 64ms
memory: 4328kb

input:

40
49999
30704571 23631198 10459697 452884 909025 3745220 5633170 29257098 24428644 21991837 21100897 21249665 18667093 13809790 21220831 32750672 29531337 31709216 17139349 4444339 787544 14509794 3855820 201034 13281440 26541636 31476242 10318360 20485824 26793325 8264891 22349828 20554718 7556006...

output:

Second
First
Second
Second
First
Second
Second
First
Second
Second
Second
First
First
First
Second
Second
Second
Second
First
First
Second
Second
Second
Second
First
First
Second
First
Second
First
First
First
First
Second
First
Second
First
First
First
First

result:

ok 40 tokens

Test #5:

score: 0
Accepted
time: 55ms
memory: 4284kb

input:

40
50000
32128601 23900639 9898059 10642201 2516432 19994626 8905808 23168114 27093651 32766595 7092623 14455293 32272254 11330578 25018676 9383756 16276912 15628227 6205425 11630483 19952395 19133325 22760569 7587885 30335157 13910732 11179526 4266775 18282905 14622912 11401940 33485172 9826535 292...

output:

First
Second
First
First
Second
Second
Second
Second
Second
First
Second
First
First
First
First
Second
First
Second
First
First
First
Second
First
First
First
Second
First
First
Second
Second
Second
First
First
First
First
First
First
Second
First
Second

result:

ok 40 tokens

Subtask #4:

score: 40
Accepted

Test #6:

score: 40
Accepted
time: 68ms
memory: 4280kb

input:

40
49035
1073176430 531291499 1005508607 675350672 368768 867368831 139504132 1321089 134482448 464248170 1068169195 68946580 469491567 738764816 742459920 535197167 531887598 672172545 609558673 608209040 335282031 532674543 72878741 610117777 138447508 398155759 71608464 672172165 402325355 609845...

output:

First
Second
First
First
Second
Second
Draw
First
Second
Draw
First
First
First
Second
First
First
First
Second
First
Draw
First
First
Draw
Second
First
Second
Second
Second
Second
Second
First
Draw
First
First
Second
First
First
First
First
First

result:

ok 40 tokens

Test #7:

score: 0
Accepted
time: 70ms
memory: 4200kb

input:

40
49531
1073150907 41944161 41943104 1073725402 1039579067 41943140 543780 1073738686 8930372 1039662046 33573892 1073200030 82948 1064763322 1073738751 34160641 1040120763 8457316 8473636 42467360 8388609 1040169947 42532869 1073656799 41959456 82977 42468453 1039663007 1073722331 8408132 2117 107...

output:

First
Draw
First
First
Second
Second
First
First
First
First
First
First
First
Second
Draw
First
Draw
Second
Second
First
Second
Second
First
Second
First
Second
Draw
Second
Second
Draw
Second
Second
Draw
Second
First
Second
Second
First
Draw
First

result:

ok 40 tokens

Test #8:

score: 0
Accepted
time: 71ms
memory: 4272kb

input:

40
49853
709415352 966616951 540711056 421879407 1063609959 653447600 235563064 576376888 527818615 672723248 544909368 778739848 928978911 891625415 1034942415 182583688 777564552 209768456 650657816 578484608 457017311 176297984 288194151 239237376 1003445863 927270735 1035976423 399464135 7864586...

output:

Second
Second
First
First
First
Draw
Second
Draw
First
Draw
Second
First
Second
Second
First
Second
Draw
First
Second
First
First
Second
First
First
Second
Draw
First
Second
Second
Draw
First
Second
Second
Second
Draw
Second
Second
Draw
First
Second

result:

ok 40 tokens

Test #9:

score: 0
Accepted
time: 69ms
memory: 4320kb

input:

40
49261
425694955 1031784295 503022575 109335829 614742016 970713959 2371605 503295718 1006601199 526379886 581191837 1037823715 69226905 537145497 612639104 972802786 648040832 536868474 536590183 8661128 1071641595 547621905 109344004 461356799 459259755 612380697 10492304 1038079850 492562410 57...

output:

First
Second
First
First
First
First
First
Second
Draw
Draw
First
Draw
Second
First
Second
Draw
First
Draw
Second
Draw
First
First
Draw
First
Second
First
Second
Second
First
First
First
Second
Second
Draw
Second
First
Draw
Draw
Second
Draw

result:

ok 40 tokens

Test #10:

score: 0
Accepted
time: 63ms
memory: 4200kb

input:

40
49583
736087491 736099826 922746303 738151902 402653272 853499890 8272 937394070 788520843 218141276 150994964 354456100 920608658 870305695 404750396 738160114 870272958 922705347 287355460 668958670 85983320 736059387 85991532 939482607 853532086 469774361 738160571 719290343 150999589 26848105...

output:

First
First
First
Draw
Draw
Second
First
First
Draw
First
Second
Second
Second
First
Draw
Second
Second
Second
Second
Second
Draw
First
Second
First
Second
First
Second
First
Second
Second
Second
Second
First
Draw
Second
Draw
Second
Draw
Second
Second

result:

ok 40 tokens

Test #11:

score: 0
Accepted
time: 64ms
memory: 4264kb

input:

40
49025
1056947963 814235909 293602565 242661882 16795396 511098874 813696000 553649153 562103809 553731077 804781306 519552763 25690373 796917759 796851710 511115003 788463611 822084357 831012865 259521018 780123647 831078400 267893247 528482043 8471808 25165825 259980026 16794112 294143236 536870...

output:

First
Second
Second
Second
First
First
Second
Second
Draw
Draw
First
Second
First
First
Draw
Second
Second
Second
Draw
First
Second
Second
First
Second
Second
First
First
First
Draw
Draw
First
Second
First
Second
Draw
Draw
Draw
First
Draw
Second

result:

ok 40 tokens

Test #12:

score: 0
Accepted
time: 73ms
memory: 4220kb

input:

40
49791
819003405 281051145 210833420 345018373 392622051 589819872 1004961788 468152307 791080944 61800429 732889056 806391811 813694977 54423523 799997944 134774795 255324134 598179832 608174085 549453824 468713460 792686563 1016168464 523698144 81297412 213979140 949555201 670040041 604606481 60...

output:

Draw
Draw
First
First
Second
Draw
Draw
Second
Second
Second
Second
First
Second
Second
Second
Second
First
First
Draw
First
First
Second
Draw
Second
First
First
Second
Second
First
Second
Draw
First
Draw
Draw
Second
First
Draw
First
Draw
Draw

result:

ok 40 tokens