CSES - HIIT Open 2017 - Results
Submission details
Task:Labyrinth
Sender:Game of Nolife
Submission time:2017-05-27 15:57:11 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.34 sdetails
#2ACCEPTED0.96 sdetails
#33.06 sdetails
#42.48 sdetails
#5ACCEPTED2.25 sdetails
#62.71 sdetails
#72.78 sdetails
#82.02 sdetails
#9ACCEPTED0.71 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"});
	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:

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