QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#850416#7334. EndgameCarroT1212AC ✓378ms101024kbC++143.2kb2025-01-10 08:34:372025-01-10 08:34:44

Judging History

This is the latest submission verdict.

  • [2025-01-10 08:34:44]
  • Judged
  • Verdict: AC
  • Time: 378ms
  • Memory: 101024kb
  • [2025-01-10 08:34:37]
  • Submitted

answer

#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9,N=8,K=6e5+7,xx[8]={-1,0,1,0,-1,-1,1,1},yy[8]={0,-1,0,1,-1,1,1,-1};
const ll J=1e18;
pii w,b,r;
int dp[K],pd[K],is[K],ind[K];
vector<int> e[K],e1[K];
bool chk(pii x) { return 0<=x.x&&x.x<8&&0<=x.y&&x.y<8; }
pii nxt(pii x,int o,int z=1) { return {x.x+xx[o]*z,x.y+yy[o]*z}; }
struct nod {
	pii w,b,r; int o;
	nod(int a=0,int s=0,int d=0,int f=0,int g=0,int h=0,int j=0) { w={a,s},b={d,f},r={g,h},o=j; }
	int get() { return ((((((w.x*N+w.y)*N+b.x)*N)+b.y)*N+r.x)*N+r.y)*2+o; }
	bool can() {
		if (w==b||b==r||w==r) return 0;
		for (int i=0;i<8;i++) if (nxt(w,i)==b) return 0;
		if (o) {
			for (int i=0;i<8;i++) if (nxt(w,i)==r) return 1;
			for (int i=0;i<8;i++) if (nxt(b,i)==r) return 0;
		}
		else {
			if (r.x==b.x&&!(w.x==r.x&&min(r.y,b.y)<=w.y&&w.y<=max(r.y,b.y))) return 0;
			if (r.y==b.y&&!(w.y==r.y&&min(r.x,b.x)<=w.x&&w.x<=max(r.x,b.x))) return 0;
		}
		return 1;
	}
};
char str[10][10];
void mian() {
	for (int i=0;i<8;i++) {
		scanf("%s",str[i]);
		for (int j=0;j<8;j++) {
			if (str[i][j]=='W') w={i,j};
			if (str[i][j]=='B') b={i,j};
			if (str[i][j]=='R') r={i,j};
		}
	}
	nod st={w.x,w.y,b.x,b.y,r.x,r.y,0};
	cout<<(pd[st.get()]+1)/2<<"\n";
}
int test(int wx,int wy,int bx,int by,int rx,int ry,int o=0) {
	return (nod){wx,wy,bx,by,rx,ry,o}.can();
}
void get(int x) {
	int a=N*N*N*N*N*N*2,b=N*N*N*N*N*2,c=N*N*N*N*2,d=N*N*N*2,e=N*N*2,f=N*2,g=2,h=1;
	printf("%d %d %d %d %d %d %d\n",x%a/b,x%b/c,x%c/d,x%d/e,x%e/f,x%f/g,x%g/h);
}
bool ORY; int main() {
	int mxx=nod{7,7,7,7,7,7,1}.get();
	for (int wx=0;wx<8;wx++) for (int wy=0;wy<8;wy++) for (int bx=0;bx<8;bx++) for (int by=0;by<8;by++)
		for (int rx=0;rx<8;rx++) for (int ry=0;ry<8;ry++) for (int o=0;o<2;o++) {
			nod s(wx,wy,bx,by,rx,ry,o);
			if (!s.can()) { is[s.get()]=1; continue; }
			if (!o) {
				for (int i=0;i<8;i++) if (chk(nxt(s.w,i))) {
					nod st=s; st.w=nxt(s.w,i),st.o^=1;
					if (st.can()) e[s.get()].pb(st.get()),e1[st.get()].pb(s.get());
				}
				for (int i=0;i<4;i++) for (int j=1;chk(nxt(s.r,i,j));j++) {
					nod st=s; st.r=nxt(s.r,i,j),st.o^=1;
					if (st.r==st.w) break;
					if (st.can()) e[s.get()].pb(st.get()),e1[st.get()].pb(s.get());
				}
			}
			else {
				ll flg=1;
				for (int i=0;i<8;i++) if (chk(nxt(s.b,i))) {
					nod st=s; st.b=nxt(s.b,i),st.o^=1;
					if (st.can()) e[s.get()].pb(st.get()),e1[st.get()].pb(s.get()),flg=0;
				}
				nod st=s; st.o^=1;
				if (flg&&st.can()) dp[s.get()]=1;
			}
		}
	queue<int> q;
	for (int i=0;i<mxx;i++) {
		ind[i]=e[i].size();
		for (int j:e[i]) assert(!is[j]);
		if (!e[i].size()&&!is[i]) {
			q.push(i);
			if (i&1^1) printf(" %d ",i),get(i);
		}
	}
	while (!q.empty()) {
		int p=q.front(); q.pop();
		if (!dp[p]) {
			for (int i:e1[p]) if (!dp[i])
				dp[i]=1,ind[i]=0,pd[i]=pd[p]+1,q.push(i);
		}
		else {
			for (int i:e1[p]) if (!dp[i]) {
				ind[i]--;
				if (!ind[i]) pd[i]=pd[p]+1,q.push(i);
			}
		}
	}
	int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 348ms
memory: 100608kb

input:

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

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


output:

1
2

result:

ok 2 number(s): "1 2"

Test #2:

score: 0
Accepted
time: 351ms
memory: 100596kb

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: 359ms
memory: 100632kb

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: 369ms
memory: 100700kb

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: 338ms
memory: 100952kb

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: 355ms
memory: 101024kb

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: 338ms
memory: 100768kb

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: 364ms
memory: 100748kb

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: 378ms
memory: 100744kb

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