QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #22456 | #2353. Maharajas are Going Home | DaBenZhongXiaSongKuaiDi# | WA | 811ms | 28224kb | C++20 | 2.4kb | 2022-03-09 18:47:46 | 2022-04-30 01:07:09 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
inline int read()
{
int n=0,f=1,ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
n=n*10+ch-'0';
ch=getchar();
}
return n*f;
}
bitset<6005>h[4005],l[4005],dj[4005],tmp;
int sg[2005][2005];
int tx[4005],ty[4005];
int main()
{
int ans=0;
for(int i=1;i<=4000;i++)
{
h[i].set();
l[i].set();
dj[i].set();
}
for(int i=1;i<=2000;i++)
{
for(int j=1;j<=2000;j++)
{
tmp.set();
tmp=tmp&h[i];
tmp=tmp&l[j];
tmp=tmp&dj[i-j+2000];
if(i>=3&&j>=2)tmp[sg[i-2][j-1]]=0;
if(i>=2&&j>=3)tmp[sg[i-1][j-2]]=0;
sg[i][j]=tmp._Find_first();
h[i][sg[i][j]]=0;
l[j][sg[i][j]]=0;
dj[i-j+2000][sg[i][j]]=0;
//if(i<=5&&j<=5)printf("%d %d %d\n",i,j,sg[i][j]);
}
}
int t,k,yh,sth;
t=read();
bool flag;
for(int greg=1;greg<=t;greg++)
{
yh=0;
k=read();
for(int i=1;i<=k;i++)
{
tx[i]=read();
ty[i]=read();
yh^=sg[tx[i]][ty[i]];
}
if(yh==0)
{
printf("-1 -1 -1\n");
continue;
}
sth=0;
for(int i=1;i<=k;i++)
{
if((sg[tx[i]][ty[i]]^yh)<sg[tx[i]][ty[i]])
{
sth=i;
break;
}
}
//printf("%d\n",sth);
flag=false;
for(int i=1;i<=tx[sth]-1;i++)
{
if(sg[i][ty[sth]]==(yh^sg[tx[sth]][ty[sth]]))
{
flag=true;
printf("%d %d %d\n",sth,i,ty[sth]);
break;
}
}
if(flag==true)continue;
for(int i=1;i<=ty[sth]-1;i++)
{
if(sg[tx[sth]][i]==(yh^sg[tx[sth]][ty[sth]]))
{
printf("%d %d %d\n",sth,tx[sth],i);
flag=true;
break;
}
}
if(flag==true)continue;
for(int i=1;i<=min(tx[sth],ty[sth])-1;i++)
{
if(sg[tx[sth]-i][ty[sth]-i]==(yh^sg[tx[sth]][ty[sth]]))
{
printf("%d %d %d\n",sth,tx[sth]-i,ty[sth]-i);
flag=true;
break;
}
}
if(flag==true)continue;
if(tx[sth]>=3&&ty[sth]>=2)
{
//printf("orz%d %d %d\n",sg[tx[sth]-2][ty[sth]-1],yh,sg[tx[sth]][ty[sth]]);
if(sg[tx[sth]-2][ty[sth]-1]==(yh^sg[tx[sth]][ty[sth]]))
{
printf("%d %d %d\n",sth,tx[sth]-2,ty[sth]-1);
flag=true;
break;
}
}
if(flag==true)continue;
if(tx[sth]>=2&&ty[sth]>=3)
{
if(sg[tx[sth]-1][ty[sth]-2]==(yh^sg[tx[sth]][ty[sth]]))
{
printf("%d %d %d\n",sth,tx[sth]-1,ty[sth]-2);
flag=true;
break;
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 785ms
memory: 28224kb
input:
3 5 2 3 3 2 3 3 3 3 3 3 1 2 4 2 1 1 3 2
output:
3 1 1 -1 -1 -1 2 1 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 802ms
memory: 28156kb
input:
1 1 1 1
output:
-1 -1 -1
result:
ok single line: '-1 -1 -1'
Test #3:
score: -100
Wrong Answer
time: 811ms
memory: 28208kb
input:
100 1 5 5 1 1 5 1 5 4 1 4 4 1 2 2 1 5 3 1 4 5 1 2 4 1 4 1 1 3 2 1 3 2 1 1 4 1 2 5 1 4 2 1 5 3 1 5 5 1 4 2 1 3 4 1 3 4 1 4 2 1 3 1 1 1 5 1 1 4 1 4 1 1 4 5 1 2 5 1 5 1 1 4 1 1 2 4 1 2 5 1 3 4 1 2 5 1 5 4 1 4 4 1 2 3 1 3 4 1 5 4 1 1 3 1 3 4 1 1 5 1 5 1 1 2 3 1 3 1 1 1 1 1 5 2 1 2 5 1 1 4 1 3 3 1 4 3 1 ...
output:
1 1 1 1 1 1 1 2 4 1 2 4 1 1 1 1 4 2 1 4 2 -1 -1 -1 1 1 1 1 1 1
result:
wrong answer 4th lines differ - expected: '1 1 1', found: '1 2 4'