— Dark mode

HIIT Open 2017

Labyrinth

  • Start: 2017-05-27 11:00:00
  • End: 2017-05-27 16:00:00
  • Contest has ended
CSES - HIIT Open 2017 - Results
Submission details
Task:Labyrinth
Sender:Game of Nolife
Submission time:2017-05-27 15:59:59 +0300
Language:C++
Status:READY
Result:
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
...
view save

correct output
YES
NO
NO
YES
YES
...
view save

user output
YES
NO
NO
YES
YES
...
view save

Test 2

Verdict: ACCEPTED

input
50
20 20
15 18
11111111111111011111
10100001010111001001
...
view save

correct output
YES
NO
YES
NO
YES
...
view save

user output
YES
NO
YES
NO
YES
...
view save

Test 3

Verdict:

input
50
30 30
3 25
110111111111111111111111111111
100010001000000000000000001001
...
view save

correct output
YES
NO
YES
NO
NO
...
view save

user output
YES
NO
YES
NO
NO
...
view save

Test 4

Verdict:

input
50
30 30
3 3
110111111111111111111111111111
100110001011010111101111110011
...
view save

correct output
NO
YES
NO
NO
YES
...
view save

user output
NO
NO
NO
NO
YES
...
view save

Test 5

Verdict: ACCEPTED

input
50
30 30
7 12
111111011111111111111111111111
100000001001100000000000010001
...
view save

correct output
YES
YES
NO
NO
NO
...
view save

user output
YES
YES
NO
NO
NO
...
view save

Test 6

Verdict: ACCEPTED

input
50
30 30
16 3
111111111111111011111111111111
111101110111011111110111011101
...
view save

correct output
NO
YES
YES
NO
YES
...
view save

user output
NO
YES
YES
NO
YES
...
view save

Test 7

Verdict:

input
50
30 30
3 22
110111111111111111111111111111
110001011111101110111011110111
...
view save

correct output
YES
YES
NO
YES
NO
...
view save

user output
YES
YES
NO
YES
NO
...
view save

Test 8

Verdict:

input
50
30 30
15 18
111111111111110111111111111111
100000000000000000000000110001
...
view save

correct output
YES
YES
NO
NO
NO
...
view save

user output
YES
YES
NO
NO
NO
...
view save

Test 9

Verdict: ACCEPTED

input
48
13 16
13 8
1111111111110111
1000000011110111
...
view save

correct output
YES
YES
YES
NO
NO
...
view save

user output
YES
YES
YES
NO
NO
...
view save

Tasks

A AlgorithmB Book writingC ContestD Dynamic duoE Epic setF FactoryG GridH HIIT gameI ImpatienceJ JonnesortK KlotskiL LabyrinthM Median string

Submissions (Game of Nolife)

2017-05-27 15:59:59 2017-05-27 15:57:59 2017-05-27 15:57:11 2017-05-27 15:51:12 2017-05-27 15:48:17 2017-05-27 15:28:29 2017-05-27 15:20:57 2017-05-27 15:19:08