QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#850527#7334. EndgameliyujiaAC ✓247ms68412kbC++171.3kb2025-01-10 09:50:212025-01-10 09:50:21

Judging History

This is the latest submission verdict.

  • [2025-01-10 09:50:21]
  • Judged
  • Verdict: AC
  • Time: 247ms
  • Memory: 68412kb
  • [2025-01-10 09:50:21]
  • Submitted

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