QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#850527 | #7334. Endgame | liyujia | AC ✓ | 247ms | 68412kb | C++17 | 1.3kb | 2025-01-10 09:50:21 | 2025-01-10 09:50:21 |
Judging History
answer
#include<bits/stdc++.h>
#define add(x)g[x].push_back(id),d[id]++
#define F(i,j,k)for(int i=j;i<=k;i++)
using namespace std;
const int N=532500;
int a[90][90],b[90][90],f[N],h[N],d[N],v[N],T;
vector<int>g[N];
int c(int x,int y,int z){
if(y%8==x%8&&x%8==z%8)x/=8,y/=8,z/=8;
else{
if(x/8!=y/8||y/8!=z/8)return 0;
x%=8,y%=8,z%=8;
}return min(y,z)<x&&x<max(y,z);
}
int main(){
F(i,0,63){
int x=i/8,y=i%8;
F(dx,max(0,x-1),min(7,x+1))F(dy,max(0,y-1),min(7,y+1))a[i][dx*8+dy]=1;
F(dy,0,7)b[i][x*8+dy]=1;
F(dx,0,7)b[i][dx*8+y]=1;a[i][i]=b[i][i]=0;
}
F(i,0,63)F(j,0,63)F(k,0,63)F(l,0,1){
int id=j<<13|l<<12|i<<6|k;
if(!l){
F(t,0,63)if(a[i][t]&&!a[k][t]&&t^j)add(id^((t^i)<<6)^4096);
F(t,0,63)if(b[j][t]&&!c(i,j,t)&&t^i)add(id^((t^j)<<13)^4096);
}else F(t,0,63)if(a[k][t]&&!a[i][t]&&(!b[j][t]||c(i,j,t)))add(id^4096^t^k^(j==t)*(j^64)<<13);
}
queue<int>q;
F(i,0,N-1)if(!d[i]&&(b[i>>13][i&63]||a[i>>6&63][i&63]))q.push(i),v[i]=1;
while(q.size()){
int t=q.front();q.pop();
for(int i:g[t])if(!f[t])
!v[i]?h[i]=h[t]+1,q.push(i),f[i]=v[i]=1:h[i]=min(h[i],h[t]+1);
else if(!v[i]){h[i]=max(h[i],h[t]+1);if(!--d[i])q.push(i),v[i]=1;}
}
cin>>T;
while(T--){
int id=0;char c;
F(i,0,63)cin>>c,id|=c=='R'?i<<13:c=='W'?i<<6:(c=='B')*i;
cout<<(h[id]+1)/2<<'\n';
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 247ms
memory: 68176kb
input:
2 ........ ........ ........ ........ ........ .......W R....... .......B ....B... ........ ..W..... ........ .....R.. ........ ........ ........
output:
1 2
result:
ok 2 number(s): "1 2"
Test #2:
score: 0
Accepted
time: 219ms
memory: 68412kb
input:
10 ........ ........ ........ ..R..... ....W... ........ .B...... ........ .......B ........ ...R.... ........ ........ ........ W....... ........ ........ .W...B.. ........ ........ ..R..... ........ ........ ........ .W...R.. ........ ........ ........ ......B. ........ ........ ........ ........
output:
7 10 9 11 11 12 11 12 14 7
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 234ms
memory: 68164kb
input:
10 ........ ...B.... ........ ......R. ........ ........ ..W..... ........ W....B.. ........ ........ ........ .R...... ........ ........ ........ ....R... ........ ..B..... ........ ........ ........ ........ .....W.. .R...... ........ ........ ........ ..B..... ........ ........ W....... ........
output:
12 9 14 13 7 7 11 13 7 7
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 223ms
memory: 68368kb
input:
10 ..B..... ........ ..W.R... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..W..... ...R.... ..B..... ........ ........ ..R..... ........ ........ ..W..... ........ ..B..... ..B..... ...R.... W....... ........ ........ ........ ........ ........ B.......
output:
1 3 3 6 2 16 16 13 7 13
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 226ms
memory: 68340kb
input:
10 .R...... ..W..B.. ........ ........ ........ ........ ........ ........ ........ ........ ......W. ........ ........ ........ ...B.... ....R... ....W... ........ .......B ........ .....R.. ........ ........ ........ ........ ........ ........ ........ .......R ....B... ........ .W...... ........
output:
8 12 9 10 11 11 14 10 7 14
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 235ms
memory: 68412kb
input:
10 ........ ......W. ........ ..R..... ...B.... ........ ........ ........ ........ ........ ........ ........ ....R... .......B ...W.... ........ ........ ...B.... ........ ........ ........ ........ ......W. .....R.. W....... ........ ..B..... ........ ........ ........ .R...... ........ ........
output:
15 6 13 14 11 10 13 12 7 11
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 242ms
memory: 68168kb
input:
10 ........ ..W..... ....R... ........ ........ B....... ........ ........ ........ ........ ...W.... .......B ........ .R...... ........ ........ ........ ........ W......R ........ ........ ........ B....... ........ ........ ........ ........ ........ R....W.. ........ ...B.... ........ ........
output:
8 8 6 10 8 15 4 6 10 11
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 243ms
memory: 68156kb
input:
10 ........ ...B.... ........ ........ ........ R....... ...W.... ........ ....B... ........ .....R.. ..W..... ........ ........ ........ ........ R...W... ........ ........ ........ ........ .B...... ........ ........ ........ ........ ........ .......W ........ .....R.. ......B. ........ ........
output:
12 2 12 5 14 5 1 11 10 8
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 243ms
memory: 68100kb
input:
10 ....B... ........ ..W..... .......R ........ ........ ........ ........ ........ ........ ..W..... ........ R....... ........ ........ ......B. .....R.. ........ ........ .......B ........ ........ ........ .......W ........ .W...... ........ ........ ........ ..R..... .B...... ........ .B......
output:
7 9 9 9 5 12 13 7 9 14
result:
ok 10 numbers