QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #69285 | #2353. Maharajas are Going Home | zhangboju# | WA | 590ms | 33080kb | C++17 | 1.7kb | 2022-12-26 11:18:15 | 2022-12-26 11:18:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;short f=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;return;
}
const int N=4005;
using node=array<int,3>;
bitset<N>h[N],l[N],d[N],tmp;
int sg[N][N];
int x[N],y[N];
void init()
{
for(int i=1;i<=4000;i++)
{
h[i].set();
l[i].set();
d[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&d[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;
d[i-j+2000][sg[i][j]]=0;
}
}
}
int main()
{
init();
int T;read(T);
while(T--)
{
int k;read(k);
int res=0;
for(int i=1;i<=k;i++)
{
read(x[i]),read(y[i]);
res^=sg[x[i]][y[i]];
}
if(res==0)
{
puts("-1 -1 -1");
continue;
}
node ans={(int)1e9,(int)1e9,0};
for(int t=1;t<=k;++t)
{
for(int i=1;i<=x[t]-1;++i)
if(sg[i][y[t]]==(res^sg[x[t]][y[t]]))
ans=min(ans,{i,y[t],t});
for(int i=1;i<=y[t]-1;++i)
if(sg[x[t]][i]==(res^sg[x[t]][y[t]]))
ans=min(ans,{x[t],i,t});
for(int i=1;i<=min(x[t],y[t])-1;++i)
if(sg[x[t]-i][y[t]-i]==(res^sg[x[t]][y[t]]))
ans=min(ans,{x[t]-i,y[t]-i,t});
if(x[t]>=3&&y[t]>=2)
if(sg[x[t]-2][y[t]-1]==(res^sg[x[t]][y[t]]))
ans=min(ans,{x[t]-2,y[t]-1,t});
if(x[t]>=2&&y[t]>=3)
if(sg[x[t]-1][y[t]-2]==(res^sg[x[t]][y[t]]))
ans=min(ans,{x[t]-1,y[t]-2,t});
}
printf("%d %d %d\n",ans[2],ans[0],ans[1]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 555ms
memory: 33068kb
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: 584ms
memory: 32868kb
input:
1 1 1 1
output:
-1 -1 -1
result:
ok single line: '-1 -1 -1'
Test #3:
score: 0
Accepted
time: 588ms
memory: 33016kb
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 1 1 1 1 1 1 4 2 1 2 4 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 -1 -1 -1 1 4 2 1 1 1 -1 -1 -1 1 2 4 1 2 4 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 1 2 4 1 1 1 1 1 1 -1 -1 -1 1 2 4 1 2 4 1 2 4 1 2 4 1 1 1 1 1 1 1 2 4 1 2 4 1 1 1 1 2 4 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 1 4 2 1 2 4 1 1 1 ...
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 590ms
memory: 33072kb
input:
100 1 10 10 1 9 8 1 2 5 1 9 10 1 3 6 1 1 2 1 1 2 1 10 6 1 6 4 1 10 8 1 7 1 1 1 3 1 4 2 1 2 1 1 1 5 1 10 4 1 6 7 1 7 2 1 7 1 1 10 2 1 4 1 1 9 3 1 9 8 1 2 2 1 2 3 1 1 9 1 3 3 1 3 9 1 9 4 1 2 2 1 6 8 1 1 3 1 3 10 1 7 6 1 10 10 1 7 8 1 2 7 1 5 3 1 8 6 1 4 4 1 9 5 1 5 1 1 2 1 1 4 1 1 3 1 1 1 9 1 5 7 1 9 ...
output:
1 1 1 1 6 5 1 2 4 1 5 6 1 2 4 1 1 1 1 1 1 1 5 6 1 2 4 1 4 2 1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 2 4 1 3 7 1 4 2 1 1 1 1 4 2 1 1 1 1 7 3 1 6 5 1 1 1 1 1 1 1 1 1 1 1 1 1 3 7 1 2 4 1 1 1 1 2 4 1 1 1 1 3 7 1 5 6 1 1 1 1 5 6 1 2 4 1 4 2 1 4 2 1 1 1 1 6 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 1 7 3 1 4 2 1 3...
result:
ok 100 lines
Test #5:
score: -100
Wrong Answer
time: 563ms
memory: 33080kb
input:
100 2 100 100 87 49 2 38 68 61 81 2 41 26 82 40 2 15 92 26 90 2 87 50 76 15 2 41 85 57 30 2 52 7 73 19 2 78 15 95 71 2 51 72 5 34 2 20 83 74 1 2 63 42 74 75 2 97 96 35 72 2 17 84 98 52 2 84 37 50 5 2 55 26 62 4 2 67 13 45 64 2 11 93 45 58 2 39 9 64 26 2 49 17 40 18 2 38 51 34 2 2 30 6 50 60 2 19 24 ...
output:
2 87 29 2 30 50 2 27 40 2 10 74 2 2 15 1 20 64 2 51 19 2 23 71 2 5 22 1 7 70 2 25 26 2 8 72 2 64 52 1 28 37 1 49 20 2 18 64 1 2 84 2 45 7 2 40 6 1 38 20 1 30 5 1 19 22 1 10 42 1 9 11 2 12 51 2 42 43 1 19 14 1 24 35 1 5 4 2 57 55 2 41 28 2 75 25 2 2 54 1 14 30 1 32 29 2 1 45 1 18 65 2 12 46 1 49 35 2...
result:
wrong answer 1st lines differ - expected: '1 91 91', found: '2 87 29'