Task: | Labyrinth |
Sender: | Game of Nolife |
Submission time: | 2017-05-27 15:57:11 +0300 |
Language: | C++ |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.34 s | details |
#2 | ACCEPTED | 0.96 s | details |
#3 | WRONG ANSWER | 3.06 s | details |
#4 | WRONG ANSWER | 2.48 s | details |
#5 | ACCEPTED | 2.25 s | details |
#6 | WRONG ANSWER | 2.71 s | details |
#7 | WRONG ANSWER | 2.78 s | details |
#8 | WRONG ANSWER | 2.02 s | details |
#9 | ACCEPTED | 0.71 s | details |
Code
#include <bits/stdc++.h> #define F first #define S second #define X real() #define Y imag() using namespace std; typedef long long ll; typedef long double ld; typedef vector<string> st; typedef complex<ld> co; vector<st> initst; vector<st> states; st init(int n, int m){ st ret(n); for (int i=0;i<n;i++){ for (int j=0;j<m;j++){ ret[i]+='1'; } } return ret; } st rot(st x){ int n=x.size(); int m=x[0].size(); st ret=init(m, n); for (int i=0;i<n;i++){ for (int ii=0;ii<m;ii++){ ret[ii][n-i-1]=x[i][ii]; } } return ret; } st mir(st x){ int n=x.size(); int m=x[0].size(); st ret=init(n, m); for (int i=0;i<n;i++){ for (int ii=0;ii<m;ii++){ ret[i][m-ii-1]=x[i][ii]; } } return ret; } void print(st x){ for (int j=0;j<(int)x.size();j++){ for (int jj=0;jj<(int)x[j].size();jj++){ cout<<x[j][jj]; } cout<<endl; } } struct trf{ int nstate; int dy,dx; }; pair<st, pair<int, int> > minim(st x){ int n=x.size(); int m=x[0].size(); int miy=n-1; int may=0; int mix=m-1; int maxx=0; for (int j=0;j<n;j++){ for (int jj=0;jj<m;jj++){ if (x[j][jj]=='0'){ miy=min(miy, j); may=max(may, j); mix=min(mix, jj); maxx=max(maxx, jj); } } } assert(miy<=may&&mix<=maxx); st ret; for (int j=miy;j<=may;j++){ string r; for (int jj=mix;jj<=maxx;jj++){ r+=x[j][jj]; } ret.push_back(r); } return {ret, {miy, mix}}; } vector<trf> g[1010]; int startstate=-1; string ma[50]; string lols[50]; int gn,gm; int can(int y, int x, int s){ if (y<0||x<0) return 0; if (y+(int)states[s].size()>gn) return 0; if (x+(int)states[s][0].size()>gm) return 0; for (int j=0;j<(int)states[s].size();j++){ for (int jj=0;jj<(int)states[s][j].size();jj++){ if (states[s][j][jj]=='0'&&ma[y+j][x+jj]=='1') return 0; } } return 1; } set<pair<pair<int, int>, int> > used; int gy,gx,gs; int fo=0; void dfs(int y, int x, int s){ if (fo) return; if (used.count({{y, x}, s})) return; used.insert({{y, x}, s}); if (!can(y, x, s)) return; for (int i=0;i<gn;i++){ lols[i]=ma[i]; } for (int i=0;i<(int)states[s].size();i++){ for (int ii=0;ii<(int)states[s][i].size();ii++){ if (states[s][i][ii]=='0') lols[y+i][x+ii]='x'; } } /* if (y+(int)states[s].size()>8){ cout<<y<<" "<<x<<" "<<s<<endl; for (int i=0;i<gn;i++){ cout<<lols[i]<<endl; } cout<<endl; }*/ if (y==gy&&x==gx&&s==gs){ fo=1; return; } for (auto nx:g[s]){ dfs(y+nx.dy, x+nx.dx, nx.nstate); } } void solve(){ for (int i=0;i<50;i++) ma[i].clear(); int n,m; cin>>n>>m; gn=n; gm=m; int a,b; cin>>a>>b; for (int i=0;i<6;i++){ for (int j=0;j<m;j++){ ma[i]+='0'; } } for (int i=6;i<n+6;i++){ cin>>ma[i]; assert((int)ma[i].size()==m); } for (int i=n+6;i<n+12;i++){ for (int j=0;j<m;j++){ ma[i]+='0'; } } gy=n+6; gx=b-1; gs=startstate; n=n+12; gn=n; used.clear(); fo=0; dfs(0, a-1, startstate); if (fo){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } } const ld PI=acos((ld)-1); int rm=1e9; ld getrand(){ int t=rand()%rm; return (ld)t/(ld)(rm-1); } ld getrand(ld a, ld b){ ld ret=a+getrand()*(b-a); assert(ret>=a&&ret<=b); return ret; } bool ccw(co a, co b, co c){ return ((c-a)*conj(b-a)).Y>0; } bool inter(co a, co b, co c, co d){ return ccw(a, d, b)!=ccw(a, c, b)&&ccw(c, a, d)!=ccw(c, b, d); } void gen(){ } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); initst.push_back({"000000"}); initst.push_back({"0000000"}); initst.push_back({"11110", "00000"}); initst.push_back({"11100", "00000"}); initst.push_back({"11100", "00001"}); initst.push_back({"11000", "00001"}); initst.push_back({"11000", "00011"}); initst.push_back({"111100", "000001"}); initst.push_back({"110000", "000111"}); initst.push_back({"11100", "00001", "01111"}); initst.push_back({"11100", "00001", "00111"}); initst.push_back({"11100", "10001", "00111"}); initst.push_back({"11000", "00011", "01111"}); initst.push_back({"11000", "10011", "00111"}); initst.push_back({"11000", "10001", "00111"}); initst.push_back({"1110", "1100", "1001", "0011"}); initst.push_back({"11100", "11001", "10011", "00111"}); initst.push_back({"1100", "1100", "1001", "0011"}); initst.push_back({"11000", "00011", "00111"}); initst.push_back({"000000", "111110"}); initst.push_back({"00011", "11001", "11100", "11110"}); initst.push_back({"111100", "000000"}); initst.push_back({"111101", "000000"}); initst.push_back({"1100", "1001", "1001", "0011", "0011"}); initst.push_back({"0011", "1011", "1001", "1100", "1110"}); initst.push_back({"0111", "0011", "1011", "1001", "1100"}); initst.push_back({"0111", "0011", "1011", "1001", "1100", "1110"}); initst.push_back({"0011", "1011", "1001", "1100", "1110"}); initst.push_back({"110", "110", "100", "101", "001", "011"}); initst.push_back({"00", "00", "01", "01", "01", "01"}); initst.push_back({"100", "100", "001", "001", "011"}); initst.push_back({"00111", "10011", "11000"}); initst.push_back({"00111", "10011", "11000", "11110"}); initst.push_back({"0111", "0011", "1000", "1110"}); for (auto t:initst){ auto nt=t; for (int i=0;i<4;i++){ for (int j=0;j<2;j++){ states.push_back(nt); nt=mir(nt); } nt=rot(nt); } } sort(states.begin(), states.end()); states.erase(unique(states.begin(), states.end()), states.end()); for (int i=0;i<(int)states.size();i++){ if (states[i].size()==6&&states[i][0].size()==1){ assert(startstate==-1); startstate=i; } } // cerr<<states.size()<<endl; assert(startstate!=-1); for (int i=0;i<(int)states.size();i++){ st t=states[i]; int n=t.size(); int m=t[0].size(); for (int j=0;j<n;j++){ for (int jj=0;jj<m;jj++){ if (t[j][jj]=='0'){ st nt=t; nt[j][jj]='1'; auto lol=minim(nt); for (int ii=0;ii<(int)states.size();ii++){ if (states[ii]==lol.F){ g[i].push_back({ii, lol.S.F, lol.S.S}); g[ii].push_back({i, -lol.S.F, -lol.S.S}); } } } } } } int tcs; cin>>tcs; for (int tc=0;tc<tcs;tc++){ solve(); } }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
16 13 16 8 13 1111111011111111 1111111011110001 ... |
correct output |
---|
YES NO NO YES YES ... |
user output |
---|
YES NO NO YES YES ... |
Test 2
Verdict: ACCEPTED
input |
---|
50 20 20 15 18 11111111111111011111 10100001010111001001 ... |
correct output |
---|
YES NO YES NO YES ... |
user output |
---|
YES NO YES NO YES ... |
Test 3
Verdict: WRONG ANSWER
input |
---|
50 30 30 3 25 110111111111111111111111111111 100010001000000000000000001001 ... |
correct output |
---|
YES NO YES NO NO ... |
user output |
---|
YES NO YES NO NO ... |
Test 4
Verdict: WRONG ANSWER
input |
---|
50 30 30 3 3 110111111111111111111111111111 100110001011010111101111110011 ... |
correct output |
---|
NO YES NO NO YES ... |
user output |
---|
NO NO NO NO YES ... |
Test 5
Verdict: ACCEPTED
input |
---|
50 30 30 7 12 111111011111111111111111111111 100000001001100000000000010001 ... |
correct output |
---|
YES YES NO NO NO ... |
user output |
---|
YES YES NO NO NO ... |
Test 6
Verdict: WRONG ANSWER
input |
---|
50 30 30 16 3 111111111111111011111111111111 111101110111011111110111011101 ... |
correct output |
---|
NO YES YES NO YES ... |
user output |
---|
NO YES YES NO YES ... |
Test 7
Verdict: WRONG ANSWER
input |
---|
50 30 30 3 22 110111111111111111111111111111 110001011111101110111011110111 ... |
correct output |
---|
YES YES NO YES NO ... |
user output |
---|
YES YES NO YES NO ... |
Test 8
Verdict: WRONG ANSWER
input |
---|
50 30 30 15 18 111111111111110111111111111111 100000000000000000000000110001 ... |
correct output |
---|
YES YES NO NO NO ... |
user output |
---|
YES YES NO NO NO ... |
Test 9
Verdict: ACCEPTED
input |
---|
48 13 16 13 8 1111111111110111 1000000011110111 ... |
correct output |
---|
YES YES YES NO NO ... |
user output |
---|
YES YES YES NO NO ... |