CSES - Putka Open 2020 – 4/5 - Results
Submission details
Task:Ruudukko
Sender:Metabolix
Submission time:2020-11-08 22:01:29 +0200
Language:C++17
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED5
#2ACCEPTED12
#3ACCEPTED27
#4ACCEPTED28
#5ACCEPTED28
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 5details
#2ACCEPTED0.01 s2, 5details
#3ACCEPTED0.01 s3, 5details
#4ACCEPTED0.01 s4, 5details
#5ACCEPTED0.01 s5details
#6ACCEPTED0.01 s5details
#7ACCEPTED0.01 s2, 5details
#8ACCEPTED0.01 s2, 5details
#9ACCEPTED0.01 s3, 5details
#10ACCEPTED0.01 s3, 5details
#11ACCEPTED0.01 s3, 5details
#12ACCEPTED0.01 s3, 5details
#13ACCEPTED0.01 s4, 5details
#14ACCEPTED0.01 s5details
#15ACCEPTED0.01 s3, 5details
#16ACCEPTED0.02 s5details

Code

#include <bits/stdc++.h>

struct lauta {
	char t[50][51] = {{0}};
	char& xy(int x, int y) {
		return t[y][x];
	}
};
struct lautaref {
	lauta* l;
	int x0, y0, w, h;
	char& xy(int x, int y) {
		return l->xy(x0 + x, y0 + y);
	}
	lautaref pala(int x0_, int y0_, int w_, int h_) {
		assert(x0_ >= 0);
		assert(y0_ >= 0);
		assert(w_ - x0_ <= w);
		assert(h_ - y0_ <= h);
		return lautaref {l, x0 + x0_, y0 + y0_, w_, h_};
	}
};

bool dfs(lautaref l, int x1, int y1, int x2, int y2, int lkm) {
	if (x1 == x2 && y1 == y2 && lkm == 0) {
		return true;
	}
	#define F(dx, dy, m) \
		if (0 <= x1 + (dx) && x1 + (dx) < l.w && 0 <= y1 + (dy) && y1 + (dy) < l.h && l.xy(x1 + (dx), y1 + (dy)) == 0) { \
			l.xy(x1, y1) = m; \
			if (dfs(l, x1 + (dx), y1 + (dy), x2, y2, lkm - 1)) return true; \
		}
	F(0, -1, 'U')
	F(0, 1, 'D')
	F(-1, 0, 'L')
	F(1, 0, 'R')
	l.xy(x1, y1) = 0;
	return false;
}

void viivaX(lautaref l, int x0, int x1, int y, char c) {
	while (x0 != x1) {
		l.xy(x0, y) = c;
		x0 += x0 < x1 ? 1 : -1;
	}
	l.xy(x0, y) = c;
}
void viivaY(lautaref l, int x, int y0, int y1, char c) {
	while (y0 != y1) {
		l.xy(x, y0) = c;
		y0 += y0 < y1 ? 1 : -1;
	}
	l.xy(x, y0) = c;
}

void kehaLURD(lautaref l) {
	viivaX(l, 0, l.w - 2, 0, 'R');
	viivaY(l, l.w - 1, 0, l.h - 2, 'D');
	viivaX(l, 1, l.w - 1, l.h - 1, 'L');
	viivaY(l, 0, 1, l.h - 1, 'U');
}

void kehaLDRU(lautaref l) {
	viivaX(l, 1, l.w - 1, 0, 'L');
	viivaY(l, l.w - 1, 1, l.h - 1, 'U');
	viivaX(l, 0, l.w - 2, l.h - 1, 'R');
	viivaY(l, 0, 0, l.h - 2, 'D');
}

void yla2(lautaref l) {
	for (int i = 0; i < l.w; ++i) {
		if (l.xy(i, 2) == 'R') {
			kehaLURD(l.pala(0, 0, l.w, 2));
			l.xy(i, 2) = 'U';
			l.xy(i+1, 1) = 'D';
			return;
		}
		if (l.xy(i, 2) == 'L') {
			kehaLDRU(l.pala(0, 0, l.w, 2));
			l.xy(i, 2) = 'U';
			l.xy(i-1, 1) = 'D';
			return;
		}
	}
}

void ala2(lautaref l) {
	for (int i = 0; i < l.w; ++i) {
		if (l.xy(i, l.h - 3) == 'R') {
			kehaLDRU(l.pala(0, l.h - 2, l.w, 2));
			l.xy(i, l.h - 3) = 'D';
			l.xy(i+1, l.h - 2) = 'U';
			return;
		}
		if (l.xy(i, l.h - 3) == 'L') {
			kehaLURD(l.pala(0, l.h - 2, l.w, 2));
			l.xy(i, l.h - 3) = 'D';
			l.xy(i-1, l.h - 2) = 'U';
			return;
		}
	}
}

void vasen2(lautaref l) {
	for (int i = 0; i < l.h; ++i) {
		if (l.xy(2, i) == 'U') {
			kehaLURD(l.pala(0, 0, 2, l.h));
			l.xy(2, i) = 'L';
			l.xy(1, i-1) = 'R';
			return;
		}
		if (l.xy(2, i) == 'D') {
			kehaLDRU(l.pala(0, 0, 2, l.h));
			l.xy(2, i) = 'L';
			l.xy(1, i+1) = 'R';
			return;
		}
	}
}

void oikea2(lautaref l) {
	for (int i = 0; i < l.h; ++i) {
		if (l.xy(l.w - 3, i) == 'U') {
			kehaLDRU(l.pala(l.w - 2, 0, 2, l.h));
			l.xy(l.w - 3, i) = 'R';
			l.xy(l.w - 2, i-1) = 'L';
			return;
		}
		if (l.xy(l.w - 3, i) == 'D') {
			kehaLURD(l.pala(l.w - 2, 0, 2, l.h));
			l.xy(l.w - 3, i) = 'R';
			l.xy(l.w - 2, i+1) = 'L';
			return;
		}
	}
}

bool ratkaise(lautaref l, int x1, int y1, int x2, int y2) {
	assert(x1 >= 0);
	assert(y1 >= 0);
	assert(x2 >= 0);
	assert(y2 >= 0);
	assert(x1 < l.w);
	assert(y1 < l.h);
	assert(x2 < l.w);
	assert(y2 < l.h);
	if ((l.w * l.h % 2 == 0) ? (x1 + y1) % 2 == (x2 + y2) % 2 : (((x1 + y1) % 2) || ((x2 + y2) % 2))) {
		return false;
	}
	if (l.w > 5 && 2 <= x1 && 2 <= x2) {
		if (ratkaise(l.pala(2, 0, l.w - 2, l.h), x1 - 2, y1, x2 - 2, y2)) {
			vasen2(l);
			return true;
		}
		return false;
	}
	if (l.h > 5 && 2 <= y1 && 2 <= y2) {
		if (ratkaise(l.pala(0, 2, l.w, l.h - 2), x1, y1 - 2, x2, y2 - 2)) {
			yla2(l);
			return true;
		}
		return false;
	}
	if (l.w > 5 && x1 < l.w - 2 && x2 < l.w - 2) {
		if (ratkaise(l.pala(0, 0, l.w - 2, l.h), x1, y1, x2, y2)) {
			oikea2(l);
			return true;
		}
		return false;
	}
	if (l.h > 5 && y1 < l.h - 2 && y2 < l.h - 2) {
		if (ratkaise(l.pala(0, 0, l.w, l.h - 2), x1, y1, x2, y2)) {
			ala2(l);
			return true;
		}
		return false;
	}
	if (l.w > 5) {
		if ((x1 == 0 || x1 == l.w - 1) && y1 == 1 && l.h == 3) {
			return false;
		}
		if ((x2 == 0 || x2 == l.w - 1) && y2 == 1 && l.h == 3) {
			return false;
		}
		if (x1 == 0) {
			if (y1 == 0) {
				kehaLDRU(l.pala(0, 0, 2, l.h));
				l.xy(1, 0) = 'R';
				return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, y1, x2 - 2, y2);
			}
			if (y1 == l.h - 1) {
				kehaLURD(l.pala(0, 0, 2, l.h));
				l.xy(1, y1) = 'R';
				return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, y1, x2 - 2, y2);
			}
			if (y1 == 1) {
				kehaLURD(l.pala(0, 0, 2, 3));
				kehaLDRU(l.pala(0, 2, 2, l.h - 2));
				l.xy(1, 3) = 'R';
				return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, y1 + 2, x2 - 2, y2);
			}
			if (y1 >= 2) {
				kehaLDRU(l.pala(0, y1 - 1, 2, l.h - y1 + 1));
				kehaLURD(l.pala(0, 0, 2, y1));
				l.xy(1, y1 - 2) = 'R';
				return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, y1 - 2, x2 - 2, y2);
			}
		}
		if (x1 == 1) {
			if (y1 == 0) {
				kehaLDRU(l.pala(0, 0, 2, l.h));
				l.xy(1, 1) = 'R';
				return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, 1, x2 - 2, y2);
			} else {
				kehaLURD(l.pala(0, 0, 2, l.h));
				l.xy(1, y1 - 1) = 'R';
				return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, y1 - 1, x2 - 2, y2);
			}
		}
		if (x1 == l.w - 1) {
			if (y1 == 0) {
				kehaLURD(l.pala(l.w - 2, 0, 2, l.h));
				l.xy(l.w - 2, 0) = 'L';
				return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 2, y1, x2, y2);
			}
			if (y1 == l.h - 1) {
				kehaLDRU(l.pala(l.w - 2, 0, 2, l.h));
				l.xy(l.w - 2, y1) = 'L';
				return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 2, y1, x2, y2);
			}
			if (y1 == 1) {
				kehaLDRU(l.pala(l.w - 2, 0, 2, 3));
				kehaLURD(l.pala(l.w - 2, 2, 2, l.h - 2));
				l.xy(l.w - 2, 3) = 'L';
				return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 2, y1 + 2, x2, y2);
			}
			if (y1 >= 2) {
				kehaLURD(l.pala(l.w - 2, y1 - 1, 2, l.h - y1 + 1));
				kehaLDRU(l.pala(l.w - 2, 0, 2, y1));
				l.xy(l.w - 2, y1 - 2) = 'L';
				return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 2, y1 - 2, x2, y2);
			}
		}
		if (x1 == l.w - 2) {
			if (y1 == 0) {
				kehaLURD(l.pala(l.w - 2, 0, 2, l.h));
				l.xy(l.w - 2, 1) = 'L';
				return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 1, 1, x2, y2);
			} else {
				kehaLDRU(l.pala(l.w - 2, 0, 2, l.h));
				l.xy(l.w - 2, y1 - 1) = 'L';
				return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 1, y1 - 1, x2, y2);
			}
		}
	}
	if (l.h > 5) {
		if ((y1 == 0 || y1 == l.h - 1) && x1 == 1 && l.w == 3) {
			return false;
		}
		if ((y2 == 0 || y2 == l.h - 1) && x2 == 1 && l.w == 3) {
			return false;
		}
		if (y1 == 0) {
			if (x1 == 0) {
				kehaLURD(l.pala(0, 0, l.w, 2));
				l.xy(0, 1) = 'D';
				return ratkaise(l.pala(0, 2, l.w, l.h - 2), x1, 0, x2, y2 - 2);
			}
			if (x1 == l.w - 1) {
				kehaLDRU(l.pala(0, 0, l.w, 2));
				l.xy(x1, 1) = 'D';
				return ratkaise(l.pala(0, 2, l.w, l.h - 2), x1, 0, x2, y2 - 2);
			}
			if (x1 == 1) {
				kehaLDRU(l.pala(0, 0, 3, 2));
				kehaLURD(l.pala(2, 0, l.w - 2, 2));
				l.xy(3, 1) = 'D';
				return ratkaise(l.pala(0, 2, l.w, l.h - 2), x1 + 2, 0, x2, y2 - 2);
			}
			if (x1 >= 2) {
				kehaLURD(l.pala(x1 - 1, 0, l.w - x1 + 1, 2));
				kehaLDRU(l.pala(0, 0, x1, 2));
				l.xy(x1 - 2, 1) = 'D';
				return ratkaise(l.pala(0, 2, l.w, l.h - 2), x1 - 2, 0, x2, y2 - 2);
			}
		}
		if (y1 == 1) {
			if (x1 == 0) {
				kehaLURD(l.pala(0, 0, l.w, 2));
				l.xy(1, 1) = 'D';
				return ratkaise(l.pala(0, 2, l.w, l.h - 2), 1, 0, x2, y2 - 2);
			} else {
				kehaLDRU(l.pala(0, 0, l.w, 2));
				l.xy(x1 - 1, 1) = 'D';
				return ratkaise(l.pala(0, 2, l.w, l.h - 2), x1 - 1, 0, x2, y2 - 2);
			}
		}
		if (y1 == l.h - 1) {
			if (x1 == 0) {
				kehaLDRU(l.pala(0, l.h - 2, l.w, 2));
				l.xy(0, l.h - 2) = 'U';
				return ratkaise(l.pala(0, 0, l.w, l.h - 2), x1, y1 - 2, x2, y2);
			}
			if (x1 == l.w - 1) {
				kehaLURD(l.pala(0, l.h - 2, l.w, 2));
				l.xy(x1, l.h - 2) = 'U';
				return ratkaise(l.pala(0, 0, l.w, l.h - 2), x1, y1 - 2, x2, y2);
			}
			if (x1 == 1) {
				kehaLURD(l.pala(0, l.h - 2, 3, 2));
				kehaLDRU(l.pala(2, l.h - 2, l.w - 2, 2));
				l.xy(3, l.h - 2) = 'U';
				return ratkaise(l.pala(0, 0, l.w, l.h - 2), x1 + 2, y1 - 2, x2, y2);
			}
			if (x1 >= 2) {
				kehaLDRU(l.pala(x1 - 1, l.h - 2, l.w - x1 + 1, 2));
				kehaLURD(l.pala(0, l.h - 2, x1, 2));
				l.xy(x1 - 2, l.h - 2) = 'U';
				return ratkaise(l.pala(0, 0, l.w, l.h - 2), x1 - 2, y1 - 2, x2, y2);
			}
		}
		if (y1 == l.h - 2) {
			if (x1 == 0) {
				kehaLDRU(l.pala(0, l.h - 2, l.w, 2));
				l.xy(1, l.h - 2) = 'U';
				return ratkaise(l.pala(0, 0, l.w, l.h - 2), 1, y1 - 1, x2, y2);
			} else {
				kehaLURD(l.pala(0, l.h - 2, l.w, 2));
				l.xy(x1 - 1, l.h - 2) = 'U';
				return ratkaise(l.pala(0, 0, l.w, l.h - 2), x1 - 1, y1 - 1, x2, y2);
			}
		}
	}
	if (l.h <= 5 && l.w <= 5) {
		return dfs(l, x1, y1, x2, y2, l.w * l.h - 1);
	}
	throw std::runtime_error("ratkaisu ei toimi");
	return false;
}

bool f(int h, int w, int y1, int x1, int y2, int x2) {
	if (h == 1) {
		if (x1 == 1 && x2 == w) {
			std::cout << "YES\n";
			while (x1 < x2) {
				std::cout << "R";
				++x1;
			}
			std::cout << "\n";
			return true;
		}
		if (x2 == 1 && x1 == w) {
			std::cout << "YES\n";
			while (x1 > x2) {
				std::cout << "L";
				--x1;
			}
			std::cout << "\n";
			return true;
		}
		std::cout << "NO\n";
		return false;
	}
	if (h == 2 && x1 == x2 && x1 != 1 && x1 != w) {
		std::cout << "NO\n";
		return false;
	}
	if (w == 2 && y1 == y2 && y1 != 1 && y1 != h) {
		std::cout << "NO\n";
		return false;
	}
	lauta l;
	int bugi = 0;
	try {
		if (!ratkaise(lautaref {&l, 0, 0, w, h}, x1 - 1, y1 - 1, x2 - 1, y2 - 1)) {
			std::cout << "NO\n";
			return false;
		}
	} catch (std::exception& e) {
		std::cout << e.what() << std::endl;
		bugi = 1;
	}
	std::cout << "YES\n";
	int x = x1, y = y1;
	for (int j = 1; j < w * h && !bugi; ++j) {
		std::cout << l.xy(x-1, y-1);
		switch (l.xy(x-1, y-1)) {
			case 'U': --y; break;
			case 'D': ++y; break;
			case 'L': --x; break;
			case 'R': ++x; break;
			default: bugi = 1;
		}
	}
	std::cout << "\n";
	if (x != x2 || y != y2 || bugi) {
		std::cout << h << ' ' << w <<  ' ' << y1 <<  ' ' << x1 <<  ' ' << y2 <<  ' ' << x2 <<  '\n';
		for (int i = 0; i < 50; ++i) for (int j = 0; j < 50; ++j) if (!l.xy(i,j)) l.xy(i,j) = ' ';
		for (int y = 0; y < h; ++y) {
			std::cout << l.t[y] << "\n";
		}
		std::cout << std::endl;
		abort();
	}
	return true;
}

int main() {
	int t = 0;
	std::cin >> t;
	if (!t) {
		for (int w = 2; w <= 15; ++w) for (int h = 2; h <= 15; ++h) {
			for (int x2 = 1; x2 <= w; ++x2) for (int x1 = 1; x1 <= w; ++x1) {
				for (int y2 = 1; y2 <= h; ++y2) for (int y1 = 1; y1 <= h; ++y1) if (x1 != x2 || y1 != y2) {
					bool mahdoton = (w * h % 2 == 0) ? (x1 + y1) % 2 == (x2 + y2) % 2 : (((x1 + y1) % 2) || ((x2 + y2) % 2));
					if (mahdoton) continue;
					f(h, w, y1, x1, y2, x2);
				}
			}
		}
		return 0;
	}
	for (int i = 0; i < t; ++i) {
		int h, w, y1, x1, y2, x2;
		if (std::cin >> h >> w >> y1 >> x1 >> y2 >> x2) {} else break;
		f(h, w, 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
...

correct output
YES
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...

user output
YES
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...

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
...

correct output
NO
NO
NO
NO
YES
...

user output
NO
NO
NO
NO
YES
...

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
...

correct output
NO
NO
NO
YES
RRRRRRRUULDLULDLULDLLUR
...

user output
NO
NO
NO
YES
RRRURDRURDRUULLLLLDLLUR
...

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
...

correct output
YES
DDRRRRRRULLLLLURRRRRULLLLLLLDD...

user output
YES
RDDRUURDDRUURDDRUUULLLLLLLDDRD...

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
...

correct output
NO
YES
LURULURULURULURULURRDDDDDDDDDR...

user output
NO
YES
UUUUUUUUUUUUUUUUULDDDDDDDDDDDD...

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
...

correct output
YES
LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL...

user output
YES
UUUUUUUUUUUUUUUULDDDDDDDDDDDDD...

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
...

correct output
YES
LLDRRRU
NO
NO
NO
...

user output
YES
LLDRRRU
NO
NO
NO
...

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
...

correct output
YES
LDRRURRDL
YES
RRRDLLLLU
NO
...

user output
YES
LDRRURRDL
YES
RRRDLLLLU
NO
...

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
...

correct output
YES
DDRRRUULLDR
NO
YES
URRRDDLULDL
...

user output
YES
DDRUURRDDLU
NO
YES
URDRURDDLLL
...

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
...

correct output
NO
NO
YES
UURRRRDDLULDLU
NO
...

user output
NO
NO
YES
UURRDRURDDLLLU
NO
...

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
...

correct output
NO
NO
NO
YES
LLLDRRRRURDRUULLLLLLLDD
...

user output
NO
NO
NO
YES
DRURDRUULLLLDDLUULLDRDL
...

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
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

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
...

correct output
YES
DDLUUURRDDDRUUU
YES
UUURRRDLDRDLLUU
NO
...

user output
YES
ULDDDRURDRUULUR
YES
UUURRRDDDLLURUL
NO
...

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
...

correct output
YES
DLDDDDDRUUUURDDDDRUURDDRRULURU...

user output
YES
RUUUURDDDDDDDDDDRUUUUUUUUUURDD...

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
...

correct output
YES
RRRRRRRUULDLULDLULDLULDLDLULDL...

user output
YES
RURDRURDRURDRUULLLLLLLDLDLULDL...

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
...

correct output
YES
DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU...

user output
YES
DDDDDDDDDDDDDDDDDDDDDRRRRRRRRR...