Code Submission Evaluation System Login

HIIT Open 2017

Start:2017-05-27 11:00:00
End:2017-05-27 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2017 - Results
History
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
Task:Labyrinth
Sender:Game of Nolife
Submission time:2017-05-27 15:59:59
Language:C++
Status:READY
Result:WRONG ANSWER

Test results

testverdicttime (s)
#1ACCEPTED0.29 / 10.00details
#2ACCEPTED1.07 / 10.00details
#3WRONG ANSWER2.81 / 10.00details
#4WRONG ANSWER3.15 / 10.00details
#5ACCEPTED3.23 / 10.00details
#6ACCEPTED2.68 / 10.00details
#7WRONG ANSWER2.75 / 10.00details
#8WRONG ANSWER2.47 / 10.00details
#9ACCEPTED0.63 / 10.00details

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
1111111011110001
1111111011110001
1111111011110001
1000000000000001
1000111011110111
1000111011110111
1000111011110111
1000000011110111
1000000011110111
1000000011110111
1111111111110111
13 16
8 13
1111111011111111
1111111011110001
...
view   save

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

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

Test 2

Verdict: ACCEPTED

input
50
20 20
15 18
11111111111111011111
10100001010111001001
11000000010101001001
10100110001100000001
11010100000100001001
10000000000000000101
10001000000000000001
10110000000000000101
11111100000000010011
10101000000000000001
11101001010000000001
10010010001100000001
10000010001000000001
11100011110000000001
10110001010110000001
10100001000100000001
10001010010001000011
...
view   save

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

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

Test 3

Verdict: WRONG ANSWER

input
50
30 30
3 25
110111111111111111111111111111
100010001000000000000000001001
100100010000000000000000001101
100000000001000000000010000011
100011000100000000000000000001
100000000000000000000000100001
100000010001000001000000000001
100000000000011010000000010101
110000000001000000000000000001
100000000000000000000000010001
101000000000000000000000000001
100000000000000000001001000101
100000000000000000010000100001
100000000000010000000010100001
100000000000000100000000010001
100000000001001000000010000001
100000000000000000000010100101
...
view   save

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

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

Test 4

Verdict: WRONG ANSWER

input
50
30 30
3 3
110111111111111111111111111111
100110001011010111101111110011
110010111111011111111011111111
100011010111111100111011101101
100001111110110111011111111001
100001111111011111110011101111
110000011101111111011111111111
111110011101101111111011100101
111110001101111110110110000101
111111010001011110111011101111
111001001111111010011111101111
111111100111101011111011111111
110111100111111111111101011111
111011010111111100101111110111
100111110000111001101011011111
110110110001011011100111011101
111101110001101001111111011111
...
view   save

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

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

Test 5

Verdict: ACCEPTED

input
50
30 30
7 12
111111011111111111111111111111
100000001001100000000000010001
100110000000000000001101000011
100100000000000000000110100001
111000000000000000000000000011
101000000000000000000000000011
100000000000000100000000000001
100000000001000000100010000001
100010000000000000000010000011
100000000100000010000000000001
100000000000000101100000000011
101000000010011001000000000011
100000010010000010000100000001
100000011010000000100000000011
100010100100000100100000001101
100100010000000000000011000001
100000000000000000000000000001
...
view   save

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

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

Test 6

Verdict: ACCEPTED

input
50
30 30
16 3
111111111111111011111111111111
111101110111011111110111011101
100000110000000000000100000001
110111011111110111011101110111
101100000000000000000000000001
100000010000000000000010000001
100000001000000000001000010001
100000110000000000000100100001
100000000100000010000000001001
111000101000000000000000000101
100000000010001100001000000001
100001000001000001000000000001
100000010000010000000000000001
100001000000100000100000000001
100000000000000000000000000011
110010000010000010000000000001
100000000001000010001110000101
...
view   save

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

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

Test 7

Verdict: WRONG ANSWER

input
50
30 30
3 22
110111111111111111111111111111
110001011111101110111011110111
110000101110111010110110111101
110000000101101110011111111001
110000010000000100000010100111
110000011100000001110111010011
100001010100000001101010111011
101101111000010100101101101111
111111111100001111111011011111
110011101110000100111111100101
110111001100000111111111101101
110011100000000011110111101101
111111110000000011111110100111
111111100100000111100110100001
111100001100000010001011011101
111011011100001100011011100111
101101110101100010101101111101
...
view   save

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

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

Test 8

Verdict: WRONG ANSWER

input
50
30 30
15 18
111111111111110111111111111111
100000000000000000000000110001
100000000000000011010000000001
101000000000000100111010000001
100000000000000110001000001001
100100000000000000010001001001
100100000000000000001000011001
101000010000010010110000100011
100000010110011100111101000001
100000100010000001000000000001
100000000100011010000000000101
101010001000000100000000000101
101001100000000110000000000001
100010000000100000000000000011
111000001001000010000000000001
110000011100000000000000001001
100001100000100000001100101001
...
view   save

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

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

Test 9

Verdict: ACCEPTED

input
48
13 16
13 8
1111111111110111
1000000011110111
1000000011110111
1000000011110111
1000111011110111
1000111011110111
1000111011110111
1000000000000001
1111111011110001
1111111011110001
1111111011110001
1111111011110001
1111111011111111
13 16
9 4
1111111101111111
1000111101111111
...
view   save

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

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