QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#850515#7334. EndgameKazemaruAC ✓412ms147904kbC++231.5kb2025-01-10 09:46:592025-01-10 09:47:00

Judging History

This is the latest submission verdict.

  • [2025-01-10 09:47:00]
  • Judged
  • Verdict: AC
  • Time: 412ms
  • Memory: 147904kb
  • [2025-01-10 09:46:59]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
const int N=2e6;
vector<int>q[N];queue<int>Q;
int a[N],c[N],d[N],f[N];char e[9][9];
#define o(x)||!x||x>8
#define d(i,j)max(abs(x##i-x##j),abs(y##i-y##j))
#define rto(x,y)((x3==x&&y3!=y&&(x1!=x||(y1!=y&&((y3<y1)^(y>y1)))))||(y3==y&&x3!=x&&(y1!=y||(x1!=x&&((x3<x1)^(x>x1))))))
#define uv f(u,-1,1)f(v,-1,1)if(u||v)add
#define mz(p,q)f(z,1,8)if(rto(p,q))add(x1,y1,x2,y2,p,q)
#define add(z...)if(y=dfs(z,!p))q[y].push_back(x),++d[x]
int dfs(int x1,int y1,int x2,int y2,int x3,int y3,int p){
	if(d(1,2)<2||!d(1,3)||(!p&&rto(x2,y2))||(p&&d(2,3)<2&&d(1,3)>1)o(x1)o(y1)o(x2)o(y2))return 0;
	int S=p*531441+x1*59049+y1*6561+x2*729+y2*81+x3*9+y3;
	if(f[S])return f[S];int x=f[S]=++l,y;a[x]=p;
	if(p)goto P;
	uv(x1+u,y1+v,x2,y2,x3,y3);
	mz(z,y3);mz(x3,z);
	return x;
	P:;
	uv(x1,y1,x2+u,y2+v,x3,y3);
	if(!d[x]&&!rto(x2,y2))return f[S]=0;
	return x;
}
inline void ycl(){
	dfs(2,2,4,4,6,6,0);
	f(i,1,l)if(!d[i])Q.push(i);
	for(;Q.size();Q.pop()){
		int x=Q.front();
		for(int y:q[x]){
			if(a[x])d[y]=min(d[y],1ll);
			if(!--d[y])c[y]=c[x]+a[x],Q.push(y);
		}
	}
}
inline void doing(){
	f(i,1,8)scanf("%s",e[i]+1);
	int x1,y1,x2,y2,x3,y3;
	f(i,1,8)f(j,1,8){
		if(e[i][j]=='W')x1=i,y1=j;
		if(e[i][j]=='B')x2=i,y2=j;
		if(e[i][j]=='R')x3=i,y3=j;
	}
	cout<<c[dfs(x1,y1,x2,y2,x3,y3,0)]<<"\n";
}
signed main(){
	int t;
	cin>>t;
	ycl();
	while(t--)doing();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 367ms
memory: 142448kb

input:

2
........
........
........
........
........
.......W
R.......
.......B

....B...
........
..W.....
........
.....R..
........
........
........


output:

1
2

result:

ok 2 number(s): "1 2"

Test #2:

score: 0
Accepted
time: 378ms
memory: 147888kb

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: 389ms
memory: 142180kb

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: 371ms
memory: 143440kb

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: 388ms
memory: 143496kb

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: 412ms
memory: 145800kb

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: 406ms
memory: 142392kb

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: 395ms
memory: 145292kb

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: 382ms
memory: 147904kb

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