QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#850416 | #7334. Endgame | CarroT1212 | AC ✓ | 378ms | 101024kb | C++14 | 3.2kb | 2025-01-10 08:34:37 | 2025-01-10 08:34:44 |
Judging History
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