CSES - Putka Open 2020 – 4/5

Submission details
Task:	Ruudukko
Sender:	Olli
Submission time:	2020-11-07 22:12:39 +0200
Language:	C++ (C++11)
Status:	READY
Result:	67

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

Test results
test	verdict	time	group
#1	WRONG ANSWER	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.04 s	5	details

Compiler report

input/code.cpp: In function 'std::__cxx11::string mirror(std::__cxx11::string)':
input/code.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); ++i) {
                 ~~^~~~~~~~~~
input/code.cpp: In function 'std::__cxx11::string upsidedown(std::__cxx11::string)':
input/code.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); ++i) {
                 ~~^~~~~~~~~~
input/code.cpp: In function 'std::__cxx11::string rotate(std::__cxx11::string)':
input/code.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); ++i) {
                 ~~^~~~~~~~~~
input/code.cpp: In function 'std::__cxx11::string solve(int, int, int, int, int, int)':
input/code.cpp:593:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < s.size();...

Code

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define F first
#define S second
#define X first
#define Y second


const int N = 55;











string mirror(string s) {
	for(int i = 0; i < s.size(); ++i) {
		if(s[i] == 'L') {
			s[i] = 'R';
		} else if (s[i] == 'R') {
			s[i] = 'L';
		}
	}
	return s;
}

string upsidedown(string s) {
	for(int i = 0; i < s.size(); ++i) {
		if(s[i] == 'U') {
			s[i] = 'D';
		} else if (s[i] == 'D') {
			s[i] = 'U';
		}
	}
	return s;
}

string reverse(string s) {
	if(s.size() == 0) return "";
	string t = "";
	for(int i = s.size() - 1; i >= 0; --i) {
		if(s[i] == 'D') {
			t += 'U';
		}
		if(s[i] == 'U') {
			t += 'D';
		}
		if(s[i] == 'L') {
			t += 'R';
		}
		if(s[i] == 'R') {
			t += 'L';
		}
	}
	return t;
}

string rotate(string s) {
	for(int i = 0; i < s.size(); ++i) {
		if(s[i] == 'D') {
			s[i] = 'L';
		} else if (s[i] == 'R') {
			s[i] = 'U';
		} else if (s[i] == 'U') {
			s[i] = 'R';
		} else {
			s[i] = 'D';
		}
	}
	return s;
}


bool z[N][N];
string cur;
bool sol;
string ans;
int am;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char di[4] = {'R', 'U', 'L', 'D'};

void dfs(int h, int w, int x2, int y2, int X, int Y) {
	if(sol) return;
	if(z[X][Y]) return;
	z[X][Y] = true;
	++am;
	if(am == h*w) {
		ans = cur;
		sol = true;
		return;
	}
	for(int i = 0; i < 4; ++i) {
		int x = X + dx[i];
		int y = Y + dy[i];
		if(x == x2 && y == y2 && am != h*w - 1) {
			continue;
		}
		if(x <= 0 || x > w || y <= 0 || y > h) continue;
		cur += di[i];
		dfs(h, w, x2, y2, x, y);
		cur.pop_back();
		if(sol) break;
	}

	--am;
	z[X][Y] = false;
}

string solveBrute(int h, int w, int x1, int y1, int x2, int y2) {
	cur = "";
	sol = false;
	ans = "";
	for(int y = 1; y <= h; ++y) {
		for(int x = 1; x <= w; ++x) {
			z[x][y] = false;
		}
	}
	am = 0;
	dfs(h, w, x2, y2, x1, y1);
	return ans;
}





string solve(int h, int w, int x1, int y1, int x2, int y2) {
	if((h*w)%2 == 0) {
		if((x1 + x2 + y1 + y2)%2 == 0) return "";
	} else {
		if((x1 + y1)%2 == 1 || (x2 + y2)%2 == 1) return "";
	}

	if(h > w) {
		return rotate(solve(w, h, y1, x1, y2, x2));
	}

	if(w <= 5) {
		return solveBrute(h, w, x1, y1, x2, y2);
	}

	if(h == 2) {
		if(y1 == 2) {
			return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2));
		}
		//y1 = 1

		if(x1 == x2) {
			if(x1 != 1 && x1 != w) {
				return "";
			}
			if(x1 == w) return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2));
			string s = "";
			for(int i = 1; i <= w-1; ++i) {
				s += 'R';
			}
			s += 'U';
			for(int i = 1; i <= w-1; ++i) {
				s += 'L';
			}
			return s;
		}

		if(x2 < x1) {
			return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2));
		}

		if(y2 == 2) {
			if((x2-x1)%2 == 1) return "";

			string s = "";
			for(int i = 1; i <= x1 - 1; ++i) {
				s += "L";
			}
			s += "U";
			for(int i = 1; i <= x1; ++i) {
				s += "R";
			}
			for(int i = 1; i <= (x2 - x1)/2 - 1; ++i) {
				s += "DRUR";
			}
			s += "DR";
			for(int i = 1; i <= (w - x2); ++i) {
				s += "R";
			}
			s += "U";
			for(int i = 1; i <= (w - x2); ++i) {
				s += "L";
			}
			return s;
		}
		//y2 = 1

		if((x2 - x1)%2 == 0) return "";
		string s = "";
		for(int i = 1; i <= x1 - 1; ++i) {
			s += "L";
		}
		s += "U";
		for(int i = 1; i <= x1-1; ++i) {
			s += "R";
		}

		for(int i = 1; i <= (x2 - x1)/2; ++i) {
			s += "RDRU";
		}
		s += "R";
		for(int i = 1; i <= w - x2; ++i) {
			s += "R";
		}
		s += "D";
		for(int i = 1; i <= w - x2; ++i) {
			s += "L";
		}
		return s;
	}


	if(h == 3) {
		if(y1 == 3) {
			return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2));
		}
		if(x2 < x1) {
			return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2));
		}


		if(x2 == x1) {
			if(y2 == 2) {
				//y1 = 1
				if(x1%2 == 1) {
					return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2));		
				}
				string s = "";
				for(int i = 1; i < x1; ++i) {
					s += "L";
				}
				s += "UU";
				for(int i = 1; i < x1/2; ++i) {
					s += "RDRU";
				}
				s += "R";
				if(w == x1) {
					s += "D";
					return s;
				}
				for(int i = 1; i <= w - x1; ++i) {
					s += "R";
				}
				s += "DD";
				for(int i = 1; i <= (w - x1 - 1)/2; ++i) {
					s += "LULD";
				}
				s += "LUL";
				return s;
			}

			if(y1 == 2) {
				return reverse(solve(h, w, x2, y2, x1, y1));
			}

			//y1 = 1 and y2 = 3
			if(x1%2 == 0) return "";
			string s = "";
			for(int i = 1; i <= x1 - 1; ++i) {
				s += "L";
			}
			s += "U";
			for(int i = 1; i <= x1/2; ++i) {
				s += "URDR";
			}

			for(int i = 1; i <= (w - x1)/2; ++i) {
				s += "RDRU";
			}
			s += "U";
			for(int i = 1; i <= (w - x1); ++i) {
				s += "L";
			}
			return s;
		}



		if(w%2 == 0) {
			if((x1 + y1)%2 == 1) {
				if(x2 > x1 + 1) {
					return "";
				}
				if(y1 == 2) {
					return "";
				}

				//x2 = x1 + 1, y1 = 1
				//x1%2 = 0
				if(y2 == 1) {

					string s = "";
					for(int i = 1; i < x1; ++i) {
						s += "L";
					}
					s += "UU";
					for(int i = 1; i <= x1/2; ++i) {
						s += "RDRU";
					}
					for(int i = 1; i <= w - x2; ++i) {
						s += "R";
					}
					s += "DD";
					for(int i = 1; i <= (w - x2)/2; ++i) {
						s += "LULD";
					}
					s += "L";
					return s;
				}

				if(y2 == 2) {
					return "";		
				}

				if(y2 == 3) {
					string s = "";
					for(int i = 1; i < x1; ++i) {
						s += "L";
					}
					s += "UU";
					for(int i = 1; i < x2/2; ++i) {
						s += "RDRU";
					}
					s += "RDRD";
					for(int i = 1; i <= w - x2; ++i) {
						s += "R";
					}
					s += "UU";
					for(int i = 1; i <= (w - x2)/2; ++i) {
						s += "LDLU";
					}
					s += "L";
					return s;
				}
			} else {
				if(y1 == 1) {
					if(y2 == 1) {
						string s = "";
						for(int i = 1; i < x1; ++i) {
							s += "L";
						}
						s += "UU";
						for(int i = 1; i <= x1/2; ++i) {
							s += "RDRU";
						}
						for(int i = 1; i <= (x2 - x1)/2; ++i) {
							s += "RDDRUU";
						}
						s += "RD";
						for(int i = 1; i <= (w - x2)/2; ++i) {
							s += "RURD";
						}
						s += "D";
						for(int i = 1; i <= w - x2; ++i) {
							s += "L";
						}
						return s;
					}
					if(y2 == 2) {
						string s = "";
						for(int i = 1; i < x1; ++i) {
							s += "L";
						}
						s += "UU";
						for(int i = 1; i <= x1/2; ++i) {
							s += "RDRU";
						}
						for(int i = 1; i < (x2 - x1)/2; ++i) {
							s += "RDDRUU";
						}
						s += "RDDR";
						for(int i = 1; i <= w - x2; ++i) {
							s += "R";
						}
						s += "UU";
						for(int i = 1; i <= (w - x2)/2; ++i) {
							s += "LDLU";
						}
						s += "LD";
						return s;
					}


					string s = "";

					for(int i = w - x1; i >= 1; --i) {
						s += "R";
					}
					s += "U";
					for(int i = 1; i <= (w - x2)/2; ++i) {
						s += "ULDL";
					}
					for(int i = 1; i <= x2 - x1; ++i) {
						s += "L";
					}
					for(int i = 1; i <= x1/2; ++i) {
						s += "LDLU";
					}
					s += "U";
					for(int i = 1; i < x2; ++i) {
						s += "R";
					}
					return s;
				} else {
					//w is even
					//x1 + y1 is even
					//y1 is 2
					if(y2 == 3) {
						return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2));
					}
					if(y2 == 1) {
						return reverse(solve(h, w, x2, y2, x1, y1));
					}
					//y2 = 2
					string s = "";
					s += "U";
					for(int i = 1; i < x1/2; ++i) {
						s += "LDLU";
					}
					s += "LDD";
					for(int i = 1; i < x1; ++i) {
						s += "R";
					}
					for(int i = 1; i <= (x2 - x1)/2; ++i) {
						s += "RUURDD";
					}
					s += "R";
					for(int i = 1; i <= (w - x2)/2; ++i) {
						s += "RURD";
					}
					s += "RUU";
					for(int i = 1; i <= w - x2; ++i) {
						s += "L";
					}
					s += "D";
					return s;
				}
			}
		} else {
			//w is odd
			if(y1 == 1 && y2 == 1) {
				//x1 and x2 are odd
				string s = "";
				for(int i = 1; i < x1; ++i) {
					s += "L";
				}
				s += "UU";
				for(int i = 1; i <= x1/2; ++i) {
					s += "RDRU";
				}
				for(int i = 1; i <= w - x1; ++i) {
					s += "R";
				}
				s += "D";
				for(int i = 1; i <= (w - x2)/2; ++i) {
					s += "DLUL";
				}
				for(int i = 1; i < x2 - x1; ++i) {
					s += "L";
				}
				s += "D";
				for(int i = 1; i < x2 - x1; ++i) {
					s += "R";
				}
				return s;
			}



			if(y1 == 1 && y2 == 2) {
				string s = "";
				for(int i = 1; i < x1; ++i) {
					s += "L";
				}
				s += "UU";
				for(int i = 1; i <= x1/2; ++i) {
					s += "RDRU";
				}

				for(int i = 1; i <= (x2 - x1)/2; ++i) {
					s += "RDDRUU";
				}
				for(int i = 1; i <= w - x2 + 1; ++i) {
					s += "R";
				}
				s += "D";
				for(int i = 1; i <= (w - x2)/2; ++i) {
					s += "DLUL";
				}
				s += "DLU";
				return s;
			}


			if(y1 == 1 && y2 == 3) {
				string s = "";
				for(int i = 1; i < x1; ++i) {
					s += "L";
				}
				s += "UU";
				for(int i = 1; i <= x1/2; ++i) {
					s += "RDRU";
				}
				for(int i = 1; i < (x2 - x1)/2; ++i) {
					s += "RDDRUU";
				}
				s += "RDD";
				for(int i = 1; i <= w - x2 + 1; ++i) {
					s += "R";
				}
				s += "UU";
				for(int i = 1; i <= (w - x2)/2; ++i) {
					s += "LDLU";
				}
				return s;
			}

			if(y1 == 2 && y2 == 2) {
				string s = "D";
				for(int i = 1; i < x1; ++i) {
					s += "L";
				}
				s += "U";
				for(int i = 1; i < x1/2; ++i) {
					s += "URDR";
				}
				s += "UR";
				for(int i = 1; i < (x2 - x1)/2; ++i) {
					s += "RDDRUU";
				}
				s += "RDDR";
				for(int i = 1; i <= w - x2; ++i) {
					s += "R";
				}
				s += "U";
				for(int i = 1; i <= (w - x2)/2; ++i) {
					s += "ULDL";
				}
				s += "ULD";
				return s;
			}

			if(y2 == 3) {
				return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2));
			}
			return reverse(solve(h, w, x2, y2, x1, y1));
		}


	}


	//h >= 4
	//also w >= 4

	if(x2 < x1) {
		return reverse(solve(h, w, x2, y2, x1, y1));
	}

	if(x1 >= 3) {
		string s = solve(h, w-2, x1-2, y1, x2-2, y2);
		int x = x1 - 2;
		int y = y1;
		string t = "";
		bool f = true;
		for(int i = 0; i < s.size(); ++i) {
			if(x == 1 && s[i] != 'R' && f) {
				t += 'L';
				if(s[i] == 'U') {
					t += solve(h, 2, 2, y, 2, y+1);
				} else {
					t += solve(h, 2, 2, y, 2, y-1);
				}
				t += 'R';
				f = false;
				continue;
			} else {
				t += s[i];
				if(s[i] == 'U') {
					++y;
				}
				if(s[i] == 'D') {
					--y;
				}
				if(s[i] == 'L') {
					--x;
				}
				if(s[i] == 'R') {
					++x;
				}
			}
		}
		return t;
	}


	if(x2 <= w - 2) {
		string s = solve(h, w-2, x1, y1, x2, y2);
		int x = x1;
		int y = y1;
		string t = "";
		bool f = true;
		for(int i = 0; i < s.size(); ++i) {
			if(x == w - 2 && s[i] != 'L' && f) {
				t += 'R';
				if(s[i] == 'U') {
					t += solve(h, 2, 1, y, 1, y+1);
				} else {
					t += solve(h, 2, 1, y, 1, y-1);
				}
				t += 'L';
				f = false;
				continue;
			} else {
				t += s[i];
				if(s[i] == 'U') {
					++y;
				}
				if(s[i] == 'D') {
					--y;
				}
				if(s[i] == 'L') {
					--x;
				}
				if(s[i] == 'R') {
					++x;
				}
			}
		}
		return t;
	}


	//x1 = 1 or 2, x2 = w or w-1


	int a = -1;
	string A = "";
	for(int i = 1; i <= h; ++i) {
		A = solve(h, 2, x1, y1, 2, i);
		if(A.size() != 0) {
			a = i;
			break;
		}
	}
	A += "R";

	A += solve(h, w-2, 1, a, x2-2, y2);
	return A;
}


int main() {
	int t;
	cin >> t;

	while(t > 0) {
		--t;

		int h, w, x1, y1, x2, y2;
		cin >> h >> w >> y1 >> x1 >> y2 >> x2;
		y1 = h+1 - y1; y2 = h+1 - y2;


		string s = solve(h, w, x1, y1, x2, y2);

		if(s.size() == 0) {
			cout << "NO\n";
		} else {
			cout << "YES\n";
			cout << s << "\n";
		}

	}


}

Test details

Test 1

Group: 1, 5

Verdict: WRONG ANSWER

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 RRRRRRRUULDLULDLULDLLUR ...` 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 ULLLLDRDRURDRRUURDDRUURDDRUURD...` 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 RRDDDDLLLUURDRUULLULLLLLLUUUUL...` 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 LDRDLDRRUUUULLLDDDDLUUUULDDDDD...` 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 RRRDDLLLURR 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 RRRRUULDLULLDR 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 URDRURDDLLLLUULDDLUULDD ...` 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 RRDDLULDLUUURRR YES RRRUUULLLDDRRUL 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 DLULDLUURRRRDDDLLLLDRRRRDLLLLL...` 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 RRRRRRRUULDLULDLULDLULDLDLLLUU...` 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

Compiler report

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 (Olli)