CSES - Putka Open 2020 – 4/5 - Results
Submission details
Task:Ruudukko
Sender:Gomhog
Submission time:2020-11-07 18:33:30 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.01 s1, 5details
#20.01 s2, 5details
#30.01 s3, 5details
#40.01 s4, 5details
#50.01 s5details
#60.01 s5details
#70.01 s2, 5details
#80.01 s2, 5details
#90.01 s3, 5details
#100.01 s3, 5details
#110.01 s3, 5details
#120.01 s3, 5details
#130.01 s4, 5details
#140.01 s5details
#150.01 s3, 5details
#160.02 s5details

Code

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F first
#define S second

using namespace std;

const string yes="YES\n";
const string no="NO\n";

int n,m;
char dir[52][52];

void createSol(int y1, int x1, int y2, int x2, int ytop, int xtop, int ybot, int xbot);

pair<int,int> nextstep(int y, int x, char c) {
	if (c=='U') return {y-1,x};
	if (c=='D') return {y+1,x};
	if (c=='L') return {y,x-1};
	if (c=='R') return {y,x+1};
	return {-1,-1};
}

bool colorCompatible(int y1, int x1, int y2, int x2, int nn, int mm) {
	return (((y1+x1+y2+x2+nn*mm)%2)==1) && ((y1+x1)%2==0 || (y2+x2)%2 == 0);
}

bool forbidden(int y1, int x1, int y2, int x2, int nn, int mm) {
	if (nn>mm) {
		swap(nn,mm);
		swap(y1,x1);
		swap(y2,x2);
	}
	if (nn==1) {
		if (y1!=1 && y1!=mm) return true;
		if (y2!=1 && y2!=mm) return true;
		return false;
	}
	if (nn==2) {
		if (x1==x2 && x1!=1 && x1!=mm) return true;
		return false;
	}
	if (nn==3) {
		if (mm%2==1) return false;
		if (x1>x2) {
			x1=mm+1-x1;
			x2=mm+1-x2;
		}
		if ((x1+y1)%2==1) return false;
		if (x1<x2-1) return true;
		if (y1==2 && x1<x2) return true;
		return false;
	}
	return false;
}

bool accept(int y1, int x1, int y2, int x2, int nn=n, int mm=m) {
	if (y1==y2 && x1==x2) return (nn==1) && (mm==1);
	return colorCompatible(y1,x1,y2,x2,nn,mm) && !forbidden(y1,x1,y2,x2,nn,mm);
}

bool tryVertSplit(int y1, int x1, int y2, int x2, int ytop, int xtop, int ybot, int xbot, int q, int r) {
	if (ytop>=q || ybot <= q) return false;
	if (y1<=q && y2 <= q) return false;
	if (y1>q && y2 > q) return false;
	if (r<=xtop || r > xbot) return false;
	if (y1 <= q) {
		if (!accept(y1-ytop,x1-xtop,q-ytop,r-xtop,q-ytop,xbot-xtop) || !accept(1,r-xtop,y2-q,x2-xtop,ybot-q,xbot-xtop)) return false;
		createSol(y1,x1,q,r,ytop,xtop,q,xbot);
		createSol(q+1,r,y2,x2,q,xtop,ybot,xbot);
		dir[q][r]='D';
		return true;
	} else {
		if (!accept(y1-q,x1-xtop,1,r-xtop,ybot-q,xbot-xtop) || !accept(q-ytop,r-xtop,y2-ytop,x2-xtop,q-ytop,xbot-xtop)) return false;
		createSol(y1,x1,q+1,r,q,xtop,ybot,xbot);
		createSol(q,r,y2,x2,ytop,xtop,q,xbot);
		dir[q+1][r]='U';
		return true;
	}
}

bool tryHoriSplit(int y1, int x1, int y2, int x2, int ytop, int xtop, int ybot, int xbot, int q, int r) {
	if (xtop>=q || xbot<=q) return false;
	if (x1<=q && x2<=q) return false;
	if (x1>q && x2>q) return false;
	if (r<=ytop || r>ybot) return false;
	if (x1<=q) {
		if (!accept(y1-ytop,x1-xtop,r-ytop,q-xtop,ybot-ytop,q-xtop) || !accept(r-ytop,1,y2-ytop,x2-q,ybot-ytop,xbot-q)) return false;
		createSol(y1,x1,r,q,ytop,xtop,ybot,q);
		createSol(r,q+1,y2,x2,ytop,q,ybot,xbot);
		dir[r][q]='R';
		return true;
	} else {
		if (!accept(y1-ytop,x1-q,r-ytop,1,ybot-ytop,xbot-q) || !accept(r-ytop,q-xtop,y2-ytop,x2-xtop,ybot-ytop,q-xtop)) return false;
		createSol(y1,x1,r,q+1,ytop,q,ybot,xbot);
		createSol(r,q,y2,x2,ytop,xtop,ybot,q);
		dir[r][q+1]='L';
		return true;
	}
}

bool trySplitting(int y1, int x1, int y2, int x2, int ytop, int xtop, int ybot, int xbot) {
	for (int i=1; ytop+i<=ybot || xbot+i<=xbot; i++) {
		if (tryVertSplit(y1,x1,y2,x2,ytop,xtop,ybot,xbot,ytop+2,xtop+i)) return true;
		if (tryVertSplit(y1,x1,y2,x2,ytop,xtop,ybot,xbot,ybot-2,xtop+i)) return true;
		if (tryHoriSplit(y1,x1,y2,x2,ytop,xtop,ybot,xbot,xtop+2,ytop+i)) return true;
		if (tryHoriSplit(y1,x1,y2,x2,ytop,xtop,ybot,xbot,xbot-2,ytop+i)) return true;
	}
	return false;
}

bool tryCut(int y1, int x1, int y2, int x2, int ytop, int xtop, int ybot, int xbot) {
	if (ytop+2<y1 && ytop+2<y2 && accept(y1-2-ytop,x1-xtop,y2-2-ytop,x2-xtop,ybot-ytop-2,xbot-xtop)) {
		createSol(y1,x1,y2,x2,ytop+2,xtop,ybot,xbot);
		for (int j=xtop+1;j<=xbot;j++) {
			if (dir[ytop+3][j]=='L') {
				dir[ytop+3][j]='U';
				for (int j2=xtop+1;j2<xbot;j2++) dir[ytop+2][j2]='R';
				dir[ytop+2][xbot]='U';
				dir[ytop+2][j-1]='D';
				for (int j2=xtop+2;j2<=xbot;j2++) dir[ytop+1][j2]='L';
				dir[ytop+1][xtop+1]='D';
				break;
			}
			if (dir[ytop+3][j]=='R') {
				dir[ytop+3][j]='U';
				for (int j2=xtop+2;j2<=xbot;j2++) dir[ytop+2][j2]='L';
				dir[ytop+2][xtop+1]='U';
				dir[ytop+2][j+1]='D';
				for (int j2=xtop+1;j2<xbot;j2++) dir[ytop+1][j2]='R';
				dir[ytop+1][xbot]='D';
				break;
			}
		}
		return true;
	}
	if (ybot-2>=y1 && ybot-2>=y2 && accept(y1-ytop,x1-xtop,y2-ytop,x2-xtop,ybot-ytop-2,xbot-xtop)) {
		createSol(y1,x1,y2,x2,ytop,xtop,ybot-2,xbot);
                for (int j=xtop+1;j<=xbot;j++) {
                        if (dir[ybot-2][j]=='L') {
                                dir[ybot-2][j]='D';
                                for (int j2=xtop+1;j2<xbot;j2++) dir[ybot-1][j2]='R';
                                dir[ybot-1][xbot]='D';
                                dir[ybot-1][j-1]='U';
                                for (int j2=xtop+2;j2<=xbot;j2++) dir[ybot][j2]='L';
                                dir[ybot][xtop+1]='U';
                                break;
                        }
                        if (dir[ybot-2][j]=='R') {
                                dir[ybot-2][j]='D';
                                for (int j2=xtop+2;j2<=xbot;j2++) dir[ybot-1][j2]='L';
                                dir[ybot-1][xtop+1]='D';
                                dir[ybot-1][j+1]='U';
                                for (int j2=xtop+1;j2<xbot;j2++) dir[ybot][j2]='R';
                                dir[ybot][xbot]='U';
                                break;
                        }
                }
                return true;
	}
	if (xtop+2<x1 && xtop+2<x2 && accept(y1-ytop,x1-xtop-2,y2-ytop,x2-xtop-2,ybot-ytop,xbot-xtop-2)) {
                createSol(y1,x1,y2,x2,ytop,xtop+2,ybot,xbot);
                for (int j=ytop+1;j<=ybot;j++) {
                        if (dir[j][xtop+3]=='U') {
                                dir[j][xtop+3]='L';
                                for (int j2=ytop+1;j2<ybot;j2++) dir[j2][xtop+2]='D';
                                dir[ybot][xtop+2]='L';
                                dir[j-1][xtop+2]='R';
                                for (int j2=ytop+2;j2<=ybot;j2++) dir[j2][xtop+1]='U';
                                dir[ytop+1][xtop+1]='R';
                                break;
                        }
                        if (dir[j][xtop+3]=='D') {
                                dir[j][xtop+3]='L';
                                for (int j2=ytop+2;j2<=ybot;j2++) dir[j2][xtop+2]='U';
                                dir[ytop+1][xtop+2]='L';
                                dir[j+1][xtop+2]='R';
                                for (int j2=ytop+1;j2<ybot;j2++) dir[j2][xtop+1]='D';
                                dir[ybot][xtop+1]='R';
                                break;
                        }
                }
                return true;
        }
	if (xbot-2>=x1 && xbot-2>=x2 && accept(y1-ytop,x1-xtop,y2-ytop,x2-xtop,ybot-ytop,xbot-xtop-2)) {
                createSol(y1,x1,y2,x2,ytop,xtop,ybot,xbot-2);
                for (int j=ytop+1;j<=ybot;j++) {
                        if (dir[j][xbot-2]=='U') {
                                dir[j][xbot-2]='R';
                                for (int j2=ytop+1;j2<ybot;j2++) dir[j2][xbot-1]='D';
                                dir[ybot-1][xbot]='R';
                                dir[ybot-1][j-1]='L';
                                for (int j2=ytop+2;j2<=ybot;j2++) dir[j2][xbot]='U';
                                dir[ytop+1][xbot]='L';
                                break;
                        }
                        if (dir[j][xbot-2]=='D') {
                                dir[j][xbot-2]='R';
                                for (int j2=ytop+2;j2<=ybot;j2++) dir[j2][xbot-1]='U';
                                dir[ytop+1][xbot-1]='R';
                                dir[j+1][xbot-1]='L';
                                for (int j2=ytop+1;j2<ybot;j2++) dir[j2][xbot]='D';
                                dir[ybot][xbot]='L';
                                break;
                        }
                }
                return true;
        }
	return false;
}

void purkka(int y1, int x1, int y2, int x2, int ytop, int xtop, int ybot, int xbot) {
	cerr<<"sori"<<endl;
}

void primeSolve(int y1, int x1, int y2, int x2, int ytop, int xtop, int ybot, int xbot) {
	if (ybot-ytop==1) {
		assert(xbot-xtop<3);
		if (x1<x2) dir[y1][x1]='R';
		else if (x1>x2) dir[y1][x1]='L';
		return;
	}
	if (xbot-xtop==1) {
		assert(ybot-ytop<3);
		if (y1<y2) dir[y1][x1]='D';
		else if (y1>y2) dir[y1][x1]='U';
		return;
	}
	if (ybot-ytop==2 && xbot-xtop==2) {
		assert((x1-x2)*(y1-y2)==0 && x1-x2+y1-y2!=0);
		if (x1==x2 && y1==y2+1) {
			if (x1==xbot) {
				dir[y1][x1]='L';
				dir[y1][x1-1]='U';
				dir[y2][x1-1]='R';
			} else {
				dir[y1][x1]='R';
				dir[y1][x1+1]='U';
				dir[y2][x1+1]='L';
			}
			return;
		}
		if (x1==x2 && y2==y1+1) {
                        if (x1==xbot) {
                                dir[y1][x1]='L';
                                dir[y1][x1-1]='D';
                                dir[y2][x1-1]='R';
                        } else {
                                dir[y1][x1]='R';
                                dir[y1][x1+1]='D';
                                dir[y2][x1+1]='L';
                        }
                        return;
                }
		if (x1==x2+1) {
			if (y1==ybot) {
				dir[y1][x1]='U';
				dir[y1-1][x1]='L';
				dir[y1-1][x2]='D';
			} else {
				dir[y1][x1]='D';
				dir[y1+1][x1]='L';
				dir[y1+1][x2]='U';
			}
			return;
		}
		if (x2==x1+1) {
			if (y1==ybot) {
                                dir[y1][x1]='U';
                                dir[y1-1][x1]='R';
                                dir[y1-1][x2]='D';
                        } else {
                                dir[y1][x1]='D';
                                dir[y1+1][x1]='R';
                                dir[y1+1][x2]='U';
                        }
                        return;
		}
	}
	if (ybot-ytop==2 && xbot-xtop==3) {
		assert(x1==x2 && x1!=xbot-1);
		if (x1==xbot) {
			dir[y1][x1]='L';
			dir[y1][x1-1]='L';
			if (y1>y2) dir[y1][x1-2]='U';
			else dir[y1][x1-2]='D';
			dir[y2][x2-2]='R';
			dir[y2][x2-1]='R';
		} else {
			dir[y1][x1]='R';
                        dir[y1][x1+1]='R';
                        if (y1>y2) dir[y1][x1+2]='U';
                        else dir[y1][x1+2]='D';
                        dir[y2][x2+2]='L';
                        dir[y2][x2+1]='L';
		}
		return;
	}
	if (ybot-ytop==3 && xbot-xtop==2) {
		assert(y1==y2 && y1!=ybot-1);
		 if (y1==ybot) {
                        dir[y1][x1]='U';
                        dir[y1-1][x1]='U';
                        if (x1>x2) dir[y1-2][x1]='L';
                        else dir[y1-2][x1]='R';
                        dir[y2-2][x2]='D';
                        dir[y2-1][x2]='D';
                } else {
                        dir[y1][x1]='D';
                        dir[y1+1][x1]='D';
                        if (x1>x2) dir[y1+2][x1]='L';
                        else dir[y1+2][x1]='R';
                        dir[y2+2][x2]='U';
                        dir[y2+1][x2]='U';
                }
                return;
	}
	if (ybot-ytop==3 && xbot-xtop==3) {
		assert((y1==ybot-1 && x1==xbot-1 && y2!=ybot-1 && x2!=xbot-1) ||
			(y1!=ybot-1 && x1!=xbot-1 && y2==ybot-1 && x2==xbot-1));
		dir[ytop+1][xtop+1]='R';
		dir[ytop+1][xtop+2]='R';
		dir[ytop+1][xtop+3]='D';
		dir[ytop+2][xtop+1]='U';
		dir[ytop+2][xtop+3]='D';
		dir[ytop+3][xtop+1]='U';
		dir[ytop+3][xtop+2]='L';
		dir[ytop+3][xtop+3]='L';
		dir[y2][x2]='G';
		if (y1==ybot-1) {
			if (y2==ybot && x2==xbot) dir[x1][y1]='D';
			else if (y2==ybot && x2==xbot-2) dir[x1][y1]='L';
			else if (y2==ybot-2 && x2==xbot) dir[x1][y1]='R';
			else if (y2==ybot-2 && x2==xbot-2) dir[x1][y1]='U';
			else assert(false);
		} else {
			if (y1==ybot && x1==xbot) dir[x1][y1-1]='L';
                        else if (y1==ybot && x1==xbot-2) dir[x1+1][y1]='U';
                        else if (y1==ybot-2 && x1==xbot) dir[x1-1][y1]='D';
                        else if (y1==ybot-2 && x1==xbot-2) dir[x1][y1+1]='R';
                        else assert(false);
		}
		return;
	}
	if (min(ybot-ytop,xbot-xtop)==4 && max(ybot-ytop,xbot-xtop)==5) {
		purkka(y1,x1,y2,x2,ytop,xtop,ybot,xbot);
	}
}


void createSol(int y1, int x1, int y2, int x2, int ytop=0, int xtop=0, int ybot=n, int xbot=m) {
	if (!tryCut(y1,x1,y2,x2,ytop,xtop,ybot,xbot)) {
		if (!trySplitting(y1,x1,y2,x2,ytop,xtop,ybot,xbot)) {
			primeSolve(y1,x1,y2,x2,ytop,xtop,ybot,xbot);
		}
	}
}

void solve(int y1, int x1, int y2, int x2) {
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) dir[i][j]='N';
	}
	dir[y2][x2]='G';
	createSol(y1,x1,y2,x2);
/*	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) cerr<<dir[i][j];
		cerr<<endl;
	}*/
	for (int i=1;i<n*m;i++) {
		cout<<dir[y1][x1];
		auto lol = nextstep(y1,x1,dir[y1][x1]);
		y1=lol.F;
		x1=lol.S;
	}
	cout<<"\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tst;
	cin>>tst;
	for (int t=0;t<tst;t++) {
		int y1,x1,y2,x2;
		cin>>n>>m>>y1>>x1>>y2>>x2;
		if (!accept(y1,x1,y2,x2)) cout<<no;
		else {
			cout<<yes;
			solve(y1,x1,y2,x2);
		}
	}
}

Test details

Test 1

Group: 1, 5

Verdict:

input
100
1 45 1 45 1 1
1 18 1 1 1 10
1 47 1 17 1 30
1 33 1 28 1 20
...

correct output
YES
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...

user output
(empty)

Error:
code: input/code.cpp:219: void primeSolve(int, int, int, int, int, int, int, int): Asserti...

Test 2

Group: 2, 5

Verdict:

input
100
2 43 1 33 1 21
2 2 1 1 2 2
2 32 1 1 2 8
2 14 1 12 1 14
...

correct output
NO
NO
NO
NO
YES
...

user output
NO
NO
NO
NO
YES
...
Truncated

Test 3

Group: 3, 5

Verdict:

input
100
3 4 2 1 2 4
3 38 2 24 1 22
3 29 2 23 2 3
3 8 3 1 1 2
...

correct output
NO
NO
NO
YES
RRRRRRRUULDLULDLULDLLUR
...

user output
(empty)

Error:
code: input/code.cpp:219: void primeSolve(int, int, int, int, int, int, int, int): Asserti...

Test 4

Group: 4, 5

Verdict:

input
100
4 25 2 19 1 5
4 13 3 10 4 12
4 7 3 1 4 2
4 23 1 19 2 5
...

correct output
YES
DDRRRRRRULLLLLURRRRRULLLLLLLDD...

user output
(empty)

Error:
code: input/code.cpp:225: void primeSolve(int, int, int, int, int, int, int, int): Asserti...

Test 5

Group: 5

Verdict:

input
100
16 8 13 1 14 8
41 21 19 11 32 12
46 17 13 7 6 11
8 41 4 32 4 12
...

correct output
NO
YES
LURULURULURULURULURRDDDDDDDDDR...

user output
NO
YES
RRRRRRRRRRDDDDDDDDDDDDDDLUUUUU...
Truncated

Error:
code: input/code.cpp:219: void primeSolve(int, int, int, int, int, int, int, int): Asserti...

Test 6

Group: 5

Verdict:

input
100
31 38 18 35 31 37
35 48 7 13 21 21
46 21 25 2 4 19
35 2 13 2 35 1
...

correct output
YES
LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL...

user output
(empty)

Error:
code: input/code.cpp:219: void primeSolve(int, int, int, int, int, int, int, int): Asserti...

Test 7

Group: 2, 5

Verdict:

input
100
2 4 1 3 1 4
2 4 2 2 1 1
2 4 2 3 1 2
2 4 2 3 1 4
...

correct output
YES
LLDRRRU
NO
NO
NO
...

user output
YES
LLDRRRU
NO
NO
NO
...
Truncated

Test 8

Group: 2, 5

Verdict:

input
100
2 5 1 2 2 4
2 5 1 2 1 1
2 5 2 1 1 2
2 5 1 1 1 5
...

correct output
YES
LDRRURRDL
YES
RRRDLLLLU
NO
...

user output
YES
LDRRURRDL
YES
RRRDLLLLU
NO
...
Truncated

Test 9

Group: 3, 5

Verdict:

input
100
3 4 1 1 2 3
3 4 2 4 3 2
3 4 2 1 3 1
3 4 1 4 3 4
...

correct output
YES
DDRRRUULLDR
NO
YES
URRRDDLULDL
...

user output
(empty)

Error:
code: input/code.cpp:219: void primeSolve(int, int, int, int, int, int, int, int): Asserti...

Test 10

Group: 3, 5

Verdict:

input
100
3 5 3 4 3 2
3 5 3 5 2 3
3 5 3 1 2 2
3 5 3 1 3 2
...

correct output
NO
NO
YES
UURRRRDDLULDLU
NO
...

user output
NO
NO
YES
UURRRRDDLULDLU
NO
...
Truncated

Test 11

Group: 3, 5

Verdict:

input
100
3 8 2 8 1 2
3 8 2 4 1 7
3 8 3 4 2 7
3 8 2 5 3 1
...

correct output
NO
NO
NO
YES
LLLDRRRRURDRUULLLLLLLDD
...

user output
(empty)

Error:
code: input/code.cpp:219: void primeSolve(int, int, int, int, int, int, int, int): Asserti...

Test 12

Group: 3, 5

Verdict:

input
100
3 9 1 3 2 9
3 9 1 6 1 5
3 9 3 6 2 8
3 9 3 2 3 4
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...
Truncated

Test 13

Group: 4, 5

Verdict:

input
100
4 4 2 2 1 4
4 4 4 1 2 2
4 4 2 1 4 3
4 4 3 1 3 3
...

correct output
YES
DDLUUURRDDDRUUU
YES
UUURRRDLDRDLLUU
NO
...

user output
YES
DRRDLLLUUURRDRU
YES
RULUURRRDDDLUUL
NO
...
Truncated

Test 14

Group: 5

Verdict:

input
100
12 27 6 22 1 8
6 25 3 2 4 4
6 16 4 6 5 2
36 33 8 6 1 6
...

correct output
YES
DLDDDDDRUUUURDDDDRUURDDRRULURU...

user output
YES
RULURULURRDDDDN...
Truncated

Error:
code: input/code.cpp:219: void primeSolve(int, int, int, int, int, int, int, int): Asserti...

Test 15

Group: 3, 5

Verdict:

input
100
3 12 3 5 1 4
3 20 3 19 2 19
3 34 3 9 2 9
3 38 2 15 3 15
...

correct output
YES
RRRRRRRUULDLULDLULDLULDLDLULDL...

user output
(empty)

Error:
code: input/code.cpp:219: void primeSolve(int, int, int, int, int, int, int, int): Asserti...

Test 16

Group: 5

Verdict:

input
100
50 50 29 1 16 21
50 50 37 5 23 48
50 50 32 22 45 24
50 50 6 28 12 37
...

correct output
YES
DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU...

user output
YES
DDDDDDDDDDDDDDDDDDDDDRRRRRRRRR...
Truncated