CSES - Putka Open 2020 – 4/5

Submission details
Task:	Ruudukko
Sender:	Gomhog
Submission time:	2020-11-09 10:49:42 +0200
Language:	C++ (C++11)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	5
#2	ACCEPTED	12
#3	ACCEPTED	27
#4	ACCEPTED	28
#5	ACCEPTED	28

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 5	details
#2	ACCEPTED	0.01 s	2, 5	details
#3	ACCEPTED	0.01 s	3, 5	details
#4	ACCEPTED	0.01 s	4, 5	details
#5	ACCEPTED	0.01 s	5	details
#6	ACCEPTED	0.01 s	5	details
#7	ACCEPTED	0.01 s	2, 5	details
#8	ACCEPTED	0.01 s	2, 5	details
#9	ACCEPTED	0.01 s	3, 5	details
#10	ACCEPTED	0.01 s	3, 5	details
#11	ACCEPTED	0.01 s	3, 5	details
#12	ACCEPTED	0.01 s	3, 5	details
#13	ACCEPTED	0.01 s	4, 5	details
#14	ACCEPTED	0.02 s	5	details
#15	ACCEPTED	0.01 s	3, 5	details
#16	ACCEPTED	0.06 s	5	details

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 (x1!=1 && x1!=mm) return true;
		if (x2!=1 && x2!=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==0) 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;
	}
	for (int q=ytop+1;q<ybot;q++) {
		for (int r=xtop+1;r<=xbot;r++) {
			if (tryVertSplit(y1,x1,y2,x2,ytop,xtop,ybot,xbot,q,r)) return true;
		}
	}
	for (int q=xtop+1;q<xbot;q++) {
		for (int r=ytop+1;r<=ybot;r++) {
			if (tryHoriSplit(y1,x1,y2,x2,ytop,xtop,ybot,xbot,q,r)) return true;
		}
	}
	return false;
}

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

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

bool tryCut(int y1, int x1, int y2, int x2, int ytop, int xtop, int ybot, int xbot) {
	if (tryVertCut(y1,x1,y2,x2,ytop,xtop,ybot,xbot,ytop+2)) return true;
	if (tryVertCut(y1,x1,y2,x2,ytop,xtop,ybot,xbot,ybot-2)) return true;
	if (tryHoriCut(y1,x1,y2,x2,ytop,xtop,ybot,xbot,xtop+2)) return true;
	if (tryHoriCut(y1,x1,y2,x2,ytop,xtop,ybot,xbot,xbot-2)) return true;
	if (tryVertCut(y1,x1,y2,x2,ytop,xtop,ybot,xbot,ytop+3)) return true;
	if (tryVertCut(y1,x1,y2,x2,ytop,xtop,ybot,xbot,ybot-3)) return true;
	if (tryHoriCut(y1,x1,y2,x2,ytop,xtop,ybot,xbot,xtop+3)) return true;
	if (tryHoriCut(y1,x1,y2,x2,ytop,xtop,ybot,xbot,xbot-3)) return true;
	return false;
}



void createSol(int y1, int x1, int y2, int x2, int ytop=0, int xtop=0, int ybot=n, int xbot=m) {
//	cerr<<"solving ("<<y1<<","<<x1<<") -> ("<<y2<<","<<x2<<") inside ("<<ytop<<","<<xtop<<") to ("<<ybot<<","<<xbot<<")"<<endl;
	if (!tryCut(y1,x1,y2,x2,ytop,xtop,ybot,xbot)) {
		if (!trySplitting(y1,x1,y2,x2,ytop,xtop,ybot,xbot)) {
			assert(ybot-ytop==1 && xbot-xtop==1);
		}
	}
/*	cerr<<"solved ("<<y1<<","<<x1<<") -> ("<<y2<<","<<x2<<") inside ("<<ytop<<","<<xtop<<") to ("<<ybot<<","<<xbot<<")"<<endl;
	for (int i=ytop+1;i<=ybot;i++) {
		for (int j=xtop+1;j<=xbot;j++) cerr<<dir[i][j];
		cerr<<endl;
	}*/
}

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: ACCEPTED

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 ...` view save

correct output
`YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...` view save

user output
`YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...` Truncated

Test 2

Group: 2, 5

Verdict: ACCEPTED

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 ...` view save

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

user output
`NO NO NO NO YES ...` Truncated

Test 3

Group: 3, 5

Verdict: ACCEPTED

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 ...` view save

correct output
`NO NO NO YES RRRRRRRUULDLULDLULDLLUR ...` view save

user output
`NO NO NO YES RRRURDRURDRUULLLLLDLLUR ...` Truncated

Test 4

Group: 4, 5

Verdict: ACCEPTED

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 ...` view save

correct output
`YES DDRRRRRRULLLLLURRRRRULLLLLLLDD...` view save

user output
`YES RRRRRRULLLLLLLDLULDLULDLULDLUL...` Truncated

Test 5

Group: 5

Verdict: ACCEPTED

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 ...` view save

correct output
`NO YES LURULURULURULURULURRDDDDDDDDDR...` view save

user output
`NO YES RRRRRRRRRRDDDDDDDDDDDDDDLUUUUU...` Truncated

Test 6

Group: 5

Verdict: ACCEPTED

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 ...` view save

correct output
`YES LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL...` view save

user output
`YES LDDDDDDDDDDDDDLUUUUUUUUUUUUULD...` Truncated

Test 7

Group: 2, 5

Verdict: ACCEPTED

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 ...` view save

correct output
`YES LLDRRRU NO NO NO ...` view save

user output
`YES LLDRRRU NO NO NO ...` Truncated

Test 8

Group: 2, 5

Verdict: ACCEPTED

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 ...` view save

correct output
`YES LDRRURRDL YES RRRDLLLLU NO ...` view save

user output
`YES LDRRURRDL YES RRRDLLLLU NO ...` Truncated

Test 9

Group: 3, 5

Verdict: ACCEPTED

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 ...` view save

correct output
`YES DDRRRUULLDR NO YES URRRDDLULDL ...` view save

user output
`YES DDRUURRDDLU NO YES URRRDDLULDL ...` Truncated

Test 10

Group: 3, 5

Verdict: ACCEPTED

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 ...` view save

correct output
`NO NO YES UURRRRDDLULDLU NO ...` view save

user output
`NO NO YES UURRRRDDLULDLU NO ...` Truncated

Test 11

Group: 3, 5

Verdict: ACCEPTED

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 ...` view save

correct output
`NO NO NO YES LLLDRRRRURDRUULLLLLLLDD ...` view save

user output
`NO NO NO YES DRURDRUULLLLDDLUULLDRDL ...` Truncated

Test 12

Group: 3, 5

Verdict: ACCEPTED

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 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 13

Group: 4, 5

Verdict: ACCEPTED

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 ...` view save

correct output
`YES DDLUUURRDDDRUUU YES UUURRRDLDRDLLUU NO ...` view save

user output
`YES DRRDLLLUUURRDRU YES RULUURRRDDDLUUL NO ...` Truncated

Test 14

Group: 5

Verdict: ACCEPTED

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 ...` view save

correct output
`YES DLDDDDDRUUUURDDDDRUURDDRRULURU...` view save

user output
`YES RULURULURRDDDDRUUUURDDDDRUUUUU...` Truncated

Test 15

Group: 3, 5

Verdict: ACCEPTED

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 ...` view save

correct output
`YES RRRRRRRUULDLULDLULDLULDLDLULDL...` view save

user output
`YES RURDRURDRURDRUULLLLLLLDLDLULDL...` Truncated

Test 16

Group: 5

Verdict: ACCEPTED

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 ...` view save

correct output
`YES DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU...` view save

user output
`YES DDDDDDDDDDDDDDDDDDDDDRRRRRRRRR...` Truncated

Putka Open 2020 – 4/5

Ruudukko

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (Gomhog)