QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#235330#5024. 【模板】双端队列xyz12325 140ms20204kbC++141.9kb2023-11-02 17:17:482023-11-02 17:17:48

Judging History

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

  • [2023-11-02 17:17:48]
  • 评测
  • 测评结果:25
  • 用时:140ms
  • 内存:20204kb
  • [2023-11-02 17:17:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long T,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an,cn,fac[1000001],inv[1000001],st[1000001],u[1000001];
char s[1000001];
struct p{long long q,w;}l[1000001];
long long pow_(long long qq,long long ww){long long ee=1;while(ww){if(ww&1) ee*=qq,ee%=mod;qq*=qq,qq%=mod,ww>>=1;}return ee%mod;}
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*f;}
void add(long long qq,long long ww){l[++o].q=ww,l[o].w=h[qq],h[qq]=o;}
long long gcd(long long qq,long long ww){return !ww?qq:gcd(ww,qq%ww);}
long long find(long long qq){return qq==fa[qq]?qq:fa[qq]=find(fa[qq]);}
void merge(long long qq,long long ww){long long f1=find(qq),f2=find(ww);if(f1==f2) return;fa[f1]=f2;}
long long C(long long qq,long long ww){return fac[qq]*inv[ww]%mod*inv[qq-ww]%mod;}
bool ch(long long ll,long long rr)
{
	bool fl=1;
	for(int i=ll;i<=rr;i++)
	{
		if(v[i]!=v[rr+ll-i]) fl=0;
	}
	return fl;
}
int main()
{
//	freopen("1.in","r",stdin);
	srand((unsigned)(time(0)^(*new int)));
	fac[0]=1;for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=pow_(fac[1000000],mod-2);for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	scanf("%lld",&T);
	for(int ii=1;ii<=T;ii++)
	{
		scanf("%lld",&a);
		long long ff=0;
		for(int i=1;i<=a;i++) scanf("%lld",&d[i]),ff^=d[i];
		if(ff==0)
		{
			printf("Draw\n");continue;
		}
		long long tt=0;
		for(int i=30;i>=0;i--)
		{
			if((1<<i)&ff)
			{
				tt=i;break;
			}
		}
		for(int i=1;i<=a;i++)
		{
			if(((1<<tt)&d[i])) v[i]=1;
			else v[i]=0;
		}
		if(a%2==0) printf("First\n");
		else
		{
			if((v[1]&&ch(2,a))||(v[a]&&ch(1,a-1)))
			{
				printf("First\n");
			}
			else printf("Second\n");
		}
	}
	return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 11ms
memory: 19212kb

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
Second
Second
Second
Draw
Draw
Draw
Draw
Second
Second
Second
Second
Second
First
Draw
Second
Second
Second
Draw
Second
Draw
Draw
First
Second
Second
Draw
Second
Second
Second
Second
Second
Second
Second
Second
First
First
Draw

result:

wrong answer 5th words differ - expected: 'First', found: 'Second'

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 12ms
memory: 19160kb

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
Second
Second
Second
Second
Second
Second
Second
Second
Draw
Second
Second
Second
Second
Second
Second
Second
Draw
Draw
Draw
Draw
Second
Second
Second
Second
Second
Second
Second
Second
Draw
Second
Second
Second
Second
Draw
Second
Second
Second
Second

result:

wrong answer 3rd words differ - expected: 'First', found: 'Second'

Subtask #3:

score: 25
Accepted

Test #4:

score: 25
Accepted
time: 136ms
memory: 20048kb

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: 140ms
memory: 20204kb

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: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 120ms
memory: 19988kb

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:

Second
Second
Second
Second
Second
Second
Draw
Second
Second
Draw
Second
Second
Second
Second
Second
Second
Second
Second
Second
Draw
Second
Second
Draw
Second
Second
Second
Second
Second
Second
Second
Second
Draw
Second
Second
Second
Second
Second
Second
Second
Second

result:

wrong answer 1st words differ - expected: 'First', found: 'Second'