CSES - HIIT Open 2017 - Results
 Task: Labyrinth Sender: Game of Nolife Submission time: 2017-05-27 15:59:59 Language: C++ Status: READY Result: WRONG ANSWER
Test results
testverdicttime
#1ACCEPTED0.29 sdetails
#2ACCEPTED1.07 sdetails
#32.81 sdetails
#43.15 sdetails
#5ACCEPTED3.23 sdetails
#6ACCEPTED2.68 sdetails
#72.75 sdetails
#82.47 sdetails
#9ACCEPTED0.63 sdetails

### 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"});
initst.push_back({"01111",
"00111",
"10001",
"11100"});
initst.push_back({"000111",
"110001",
"111100"});
initst.push_back({"110",
"110",
"100",
"001",
"011",
"011"});
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:

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:

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: ACCEPTED

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:

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:

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
...