CSES - Putka Open 2020 – 4/5

CSES - Putka Open 2020 – 4/5 - Results

Submission details
Task:	Ruudukko
Sender:	mango_lassi
Submission time:	2020-11-08 22:25:54 +0200
Language:	C++ (C++11)
Status:	READY
Result:	72

Feedback
group	verdict	score
#1	ACCEPTED	5
#2	ACCEPTED	12
#3	ACCEPTED	27
#4	ACCEPTED	28
#5	TIME LIMIT EXCEEDED	0

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	TIME LIMIT EXCEEDED	--	5	details
#15	ACCEPTED	0.01 s	3, 5	details
#16	TIME LIMIT EXCEEDED	--	5	details

Compiler report

input/code.cpp: In function 'std::vector<std::pair<int, int> > join(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
input/code.cpp:144:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + 1 < a.size(); ++i) {
                  ~~~~~~^~~~~~~~~~
input/code.cpp:149:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = i+1; j < a.size(); ++j) res.push_back(a[j]);
                      ~~^~~~~~~~~~
input/code.cpp:155:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = i+1; j < a.size(); ++j) res.push_back(a[j]);
                      ~~^~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using point = pair<int, int>;


string rev(string str) {
	for (auto& c : str) {
		if (c == 'L') c = 'R';
		else if (c == 'R') c = 'L';
		else if (c == 'D') c = 'U';
		else c = 'D';
	}
	reverse(str.begin(), str.end());
	return str;
}

string solveSmall(int h, int w, int y0, int x0, int y1, int x1) {
	if (x0 > x1 || (x0 == x1 && y0 > y1)) return rev(solveSmall(h, w, y1, x1, y0, x0));

	if (h == 1) {
		if (x0 == 0 && x1 == w-1) return string(w-1, 'R');
		if (x0 == w-1 && x1 == 0) return string(w-1, 'L');
		return "";
	} else {
		if (x0 == x1 && 0 < x0 && x0 < w-1) return "";

		string res;
		if (x0 == x1 && x0 == 0) {
			for (int i = 0; i < w-1; ++i) res.push_back('R');

			if (y0 == 0) res.push_back('U');
			else res.push_back('D');

			for (int i = 0; i < w-1; ++i) res.push_back('L');

		} else {
			for (int i = 0; i < x0; ++i) res.push_back('L');

			if (y0 == 0) res.push_back('U');
			else res.push_back('D');

			for (int i = 0; i < x0; ++i) res.push_back('R');

			if (x0 == x1) return res;

			for (int i = 0; i < x1 - x0 - 1; ++i) {
				res.push_back('R');
				if ((i ^ y0) & 1) res.push_back('U');
				else res.push_back('D');
			}
			res.push_back('R');

			for (int i = 0; i < w-1 - x1; ++i) res.push_back('R');

			if (y1 == 0) res.push_back('D');
			else res.push_back('U');

			for (int i = 0; i < w-1 - x1; ++i) res.push_back('L');
		}
		
		return res;
	}
}












const int N = 60;
int ord[N][N];

bool recBrute(int h, int w, int y, int x, int ty, int tx, int i) {
	if (y < 0 || y >= h || x < 0 || x >= w) return false;
	if (ord[y][x] != -1) return false;

	ord[y][x] = i;
	if (y == ty && x == tx) {
		if (i == h*w - 1) return true;
	} else {
		for (int dx = -1; dx <= 1; dx += 2) {
			if (recBrute(h, w, y, x + dx, ty, tx, i+1)) return true;
		}
		for (int dy = -1; dy <= 1; dy += 2) {
			if (recBrute(h, w, y + dy, x, ty, tx, i+1)) return true;
		}
	}
	ord[y][x] = -1;
	return false;
}

vector<point> brute(int h, int w, int y0, int x0, int y1, int x1) {
	// cerr << "brute(" << h << ' ' << w << ' ' << y0 << ' ' << x0 << ' ' << y1 << ' ' << x1 << endl;

	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) ord[y][x] = -1;
	}

	bool res = recBrute(h, w, y0, x0, y1, x1, 0);
	// if (! res) return {};
	assert(res);

	vector<point> ans(h*w);
	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) {
			ans[ord[y][x]] = {y, x};
		}
	}

	return ans;
}

bool works(int h, int w, int y0, int x0, int y1, int x1) {
	if (y0 == y1 && x0 == x1) return false;
	if (w < h) return works(w, h, x0, y0, x1, y1);
	if (! ((h*w ^ abs(x0 - x1) ^ abs(y0 - y1)) & 1)) return false;
	if ((h*w & 1) && ((x0 + y0) & 1)) return false;

	if (h <= 2) return !solveSmall(h, w, y0, x0, y1, x1).empty();
	if (h == 3 && (!(w & 1))) {
		if (y0 == 1) {
			if ((x0 & 1) && x1 < x0) return false;
			if (!(x0 & 1) && x1 > x0) return false;
		} else {
			if (!(x0 & 1) && (x1 < x0 - 1)) return false;
			if ((x0 & 1) && (x1 > x0 + 1)) return false;
		}
	}
	return true;
}

bool adj(point a, point b) {
	return (abs(a.first - b.first) + abs(a.second - b.second) == 1);
}

vector<point> join(vector<point> a, vector<point> b) {
	for (int i = 0; i + 1 < a.size(); ++i) {
		if (adj(a[i], b[0]) && adj(a[i+1], b.back())) {
			vector<point> res;
			for (int j = 0; j <= i; ++j) res.push_back(a[j]);
			for (auto pr : b) res.push_back(pr);
			for (int j = i+1; j < a.size(); ++j) res.push_back(a[j]);
			return res;
		} else if (adj(a[i], b.back()) && adj(a[i+1], b[0])) {
			vector<point> res;
			for (int j = 0; j <= i; ++j) res.push_back(a[j]);
			for (int j = (int)b.size() - 1; j >= 0; --j) res.push_back(b[j]);
			for (int j = i+1; j < a.size(); ++j) res.push_back(a[j]);
			return res;
		}
	}
	assert(0);
	return {}; // Fail
}

vector<point> shift(vector<point> ans, int dy, int dx) {
	for (point& p : ans) {
		p.first += dy;
		p.second += dx;
	}
	return ans;
}
vector<point> mirror(vector<point> ans, int dy, int dx, int h, int w) {
	for (point& p : ans) {
		if (dy == -1) p.first = h-1 - p.first;
		if (dx == -1) p.second = w-1 - p.second;
	}
	return ans;
}
vector<point> flip(vector<point> ans) {
	for (point& p : ans) {
		swap(p.first, p.second);
	}
	return ans;
}
vector<point> concat(vector<point> a, vector<point> b) {
	vector<point> res;
	for (auto pr : a) res.push_back(pr);
	for (auto pr : b) res.push_back(pr);
	return res;
}

vector<point> solve(int h, int w, int y0, int x0, int y1, int x1) {

	// cerr << "solve(" << h << ' ' <<  w << ' ' << y0 << ' ' << x0 << ' ' << y1 << ' ' << x1 << ")\n";

	// Fill sides

	// cerr << works(h, w-2, y0, x0 - 2, y1, x1 - 2) << ' ' << works(h, w-2, y0, (x0

	if (x0 >= 3 && x1 >= 3 && works(h, w - 2, y0, x0 - 2, y1, x1 - 2)) {

		vector<point> a = shift(solve(h, w - 2, y0, x0 - 2, y1, x1 - 2), 0, 2);

		vector<point> b;
		for (int y = 1; y < h; ++y) b.push_back({y, 1});
		for (int y = h-1; y >= 0; --y) b.push_back({y, 0});
		b.push_back({0, 1});

		return join(a, b);
	}

	if (x0 < w - 3 && x1 < w - 3 && works(h, w - 2, y0, x0, y1, x1)) {

		// cerr << "cut edge 1\n";
		return mirror(solve(h, w, y0, w-1 - x0, y1, w-1 - x1), 1, -1, h, w);
	}

	if (y0 >= 3 && y1 >= 3 && works(h - 2, w, y0 - 2, x0, y1 - 2, x1)) {

		// cerr << "cut edge 2\n";
		return flip(solve(w, h, x0, y0, x1, y1));
	}

	if (x0 < w - 3 && x1 < w - 3 && works(h - 2, w, y0, x0, y1, x1)) {

		// cerr << "cut edge 3\n";
		return flip(solve(w, h, x0, y0, x1, y1));
	}

	// Cut center
	if (abs(x0 - x1) < abs(y0 - y1)) {
		// cerr << "inc abs\n";
		return flip(solve(w, h, x0, y0, x1, y1));
	}
	if (x0 > x1) {
		// cerr << "fix ord\n";
		return mirror(solve(h, w, y0, w-1-x0, y1, w-1-x1), 1, -1, h, w);
	}

	// cerr << "start splitting " << h << ' ' <<  w << ' ' << y0 << ' ' << x0 << ' ' << y1 << ' ' << x1 << ")\n";

	for (int x = x0; x < x1; ++x) {
		for (int y = 0; y < h; ++y) {
			// cerr << x << ' ' << y << ": " << works(h, x+1, y0, x0, y, x) << ' ' << works(h, w-(x+1), y, 0, y1, x1 - (x+1)) << '\n';

			if (works(h, x+1, y0, x0, y, x) && works(h, w-(x+1), y, 0, y1, x1 - (x+1))) {
				return concat(solve(h, x+1, y0, x0, y, x), shift(solve(h, w-(x+1), y, 0, y1, x1 - (x+1)), 0, x + 1));
			}
		}
	}

	// Nothing works, so it must be small, right?? right???
	return brute(h, w, y0, x0, y1, x1);
}

string convert(vector<point> ans) {
	int n = ans.size();
	if (ans.empty()) return "";

	string res(n-1, '_');
	for (int i = 0; i < n; ++i) {
		if (ans[i+1].first > ans[i].first) res[i] = 'D';
		if (ans[i+1].first < ans[i].first) res[i] = 'U';
		if (ans[i+1].second > ans[i].second) res[i] = 'R';
		if (ans[i+1].second < ans[i].second) res[i] = 'L';
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	// cout << t << '\n';

	for (int ti = 0; ti < t; ++ti) {
		int h, w, y0, x0, y1, x1;
		cin >> h >> w >> y0 >> x0 >> y1 >> x1;
		--x0; --y0; --x1; --y1;

		// cout << h << ' ' << w << ' ' << y0 << ' ' << x0 << ' ' << y1 << ' ' << x1 << '\n';
		
		if (! works(h, w, y0, x0, y1, x1)) cout << "NO\n";
		else {
			string res = convert(solve(h, w, y0, x0, y1, x1));
			cout << "YES\n" << res << '\n';
		}
	}
}

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 DDRRULURRDDRUURDDRUUULLLLLLLDD...` 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 LLUURDRURULLLURRRULLLURRRULLLU...` 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 RRRULLLLURRRRULLLLURRRRULLLLUR...` 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 DDLUUURRDDDRUUU YES RRRUUULDDLLUURD NO ...` Truncated

Test 14

Group: 5

Verdict: TIME LIMIT EXCEEDED

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

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: TIME LIMIT EXCEEDED

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

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