Code Submission Evaluation System Login

# HIIT Open 2017

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

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

 test verdict time (s) #1 ACCEPTED 0.29 / 10.00 details #2 ACCEPTED 1.07 / 10.00 details #3 WRONG ANSWER 2.81 / 10.00 details #4 WRONG ANSWER 3.15 / 10.00 details #5 ACCEPTED 3.23 / 10.00 details #6 ACCEPTED 2.68 / 10.00 details #7 WRONG ANSWER 2.75 / 10.00 details #8 WRONG ANSWER 2.47 / 10.00 details #9 ACCEPTED 0.63 / 10.00 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"});
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

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

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

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

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