CSES - Putka Open 2020 – 4/5

CSES - Putka Open 2020 – 4/5 - Results

Submission details
Task:	Ruudukko
Sender:	Sisuaski
Submission time:	2020-11-08 17:28:12 +0200
Language:	C++17
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.02 s	5	details
#6	ACCEPTED	0.02 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.07 s	5	details

Code

#include <iostream>
#include <complex>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef complex<int> C;

char used[64][64];

constexpr C ds[] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
constexpr char dcs[2][5] = {"RDLU", "LURD"};

char& get(C c) {
	return used[c.imag()][c.real()];
}

int fcount(C c) {
	int r=0;
	for(C d: ds) r += get(c+d)<2;
	return r;
}
int fcount2(C c) {
	int r=0;
	for(C d: ds) r += get(c+d)==0;
	return r;
}
int ucount(C c) {
	int r=0;
	for(C d: ds) r += get(c+d);
	return r;
}
int bcount(C c) {
	int r=0;
	for(C d: ds) {
		if (get(c+d)) continue;
		r += max(ucount(c+d)-2, 0);
	}
	return r;
}

int dist(C c) {
	return c.real()*c.real() + c.imag()*c.imag();
}

int N,M;
bool onWall(C c) {
	return c.real()==1 || c.real()==M || c.imag()==1 || c.imag()==N;
}

void dump() {
	string s(M, '\0');
	for(int i=1; i<=N; ++i) {
		for(int j=1; j<=M; ++j) s[j-1]=used[i][j]==0 ? '.' : used[i][j]==1 ? '*' : '#';
		cout<<s<<'\n';
	}
}

int conn[64][64];
int CT = 1;
void dfs(C cur) {
	conn[cur.imag()][cur.real()] = CT;
	for(C d: ds) {
		C c = cur+d;
		if (get(c) || conn[c.imag()][c.real()]==CT) continue;
		dfs(c);
	}
}

bool isConnected(C from, C to) {
	CT++;
	int oldFrom = get(from);
	int oldTo = get(to);
	get(from) = 1;
	get(to) = 1;
	bool found = 0;
	bool ok = 1;
	for(int i=1; i<=N; ++i) {
		for(int j=1; j<=M; ++j) {
			if (used[i][j]) continue;
			if (found) {
				if (conn[i][j] != CT) {
//					cout<<"fail "<<i<<' '<<j<<" : "<<conn[i][j]<<" / "<<CT<<'\n';
					ok = 0;
					goto end;
				}
			} else {
				dfs({j,i});
				found = 1;
			}
		}
	}
end:
	get(from) = oldFrom;
	get(to) = oldTo;
	return ok;
}

pair<int,int> getRanges() {
	int minx=M, maxx=0, miny=N, maxy=0;
	for(int i=1; i<=N; ++i) for(int j=1; j<=M; ++j) if (!used[i][j]) {
		minx = min(minx, j);
		maxx = max(maxx, j);
		miny = min(miny, i);
		maxy = max(maxy, i);
	}
	return {maxx-minx, maxy-miny};
}

string go(C from, C to, int targetSize) {
	if ((abs(from.real()-to.real()) + abs(from.imag()-to.imag()) + targetSize) & 1) {
		return "";
	}
	if (!isConnected(from, to)) return "";
	string oldUsed(&used[0][0], sizeof(used));

	string res[2];
	C cur[2] = {from, to};
	vector<pair<int,int>> bs;
	while(1) {
		get(cur[0]) = get(cur[1]) = 1;
//		cout<<"cur "<<cur[0]<<' '<<cur[1]<<'\n';
//		dump();

		bs.clear();
		int best=-1e9;
		int cnts[2] = {};

		for(int a=0; a<2; ++a) {
			for(int i=0; i<4; ++i) {
				if (!get(cur[a]+ds[i]) && fcount(cur[a]+ds[i])==2 && fcount2(cur[a]+ds[i]) == 1) {
					if (!bs.empty() && bs.back().first == a) goto end;
					bs.emplace_back(a,i);
				}
			}
		}
		if (!bs.empty()) {
			bs.resize(1);
			goto skip;
		}

		for(int a=0; a<2; ++a) for(C d:ds) cnts[a] += !get(cur[a]+d);
		for(int a=0; a<2; ++a) {
			if (cnts[a] != min(cnts[0],cnts[1])) continue;

			if (onWall(cur[a]) &&
					((!get(cur[a]+ds[0]) && !get(cur[a]+ds[2]))
					|| (!get(cur[a]+ds[1]) && !get(cur[a]+ds[3])))) {
				for(int i=0; i<4; ++i) {
					if (get(cur[a] + ds[i])) continue;
//					cout<<"forking...\n";
//					dump();
					get(cur[a]) = 2;
					cur[a] += ds[i];
					res[a] += dcs[a][i];

					string rr = go(cur[0], cur[1], targetSize - res[0].size() - res[1].size());
//					cout<<"res size: "<<res[0].size()<<' '<<res[1].size()<<' '<<rr.size()<<" ; "<<targetSize<<'\n';
					if (int(res[0].size() + res[1].size() + rr.size()) == targetSize) {
						res[0] += rr;
						reverse(res[1].begin(), res[1].end());
						return res[0] + res[1];
					}

					res[a].erase(res[a].end()-1);
					cur[a] -= ds[i];
					get(cur[a]) = 1;
				}
				continue;
			}

			for(int i=0; i<4; ++i) {
				C c = cur[a] + ds[i];
				if (get(c)) continue;
				int d = dist(c - cur[1-a]);
				int f = fcount(c);
				int b = bcount(c);
				int val = 1e6*(4-f) + d;
				val -= 1e7*max(b-3, 0);
//				cout<<"choice "<<a<<' '<<i<<' '<<c<<" : "<<d<<' '<<f<<' '<<b<<'\n';
				if (val > best) bs.clear(),best=val;
				if (val >= best) {
					if (bs.empty() || bs.back().first == a) {
						bs.emplace_back(a,i);
					}
				}
			}
		}
skip:
		if (bs.empty()) break;
		constexpr int L = 6;
		if (bs.size()==1 || (abs(cur[0].real()-cur[1].real())>L && abs(cur[0].imag()-cur[1].imag())>L)) {
cancelfork:
			auto [a,i] = bs[0];
			get(cur[a]) = 2;
			res[a] += dcs[a][i];
			cur[a] += ds[i];
		} else {
			pair ranges = getRanges();
//			cout<<"ranges: "<<ranges.first<<' '<<ranges.second<<'\n';
			if (ranges.first >= L && ranges.second >= L) goto cancelfork;
			for(auto [a,i] : bs) {
//				cout<<"eq forking...\n";
//				dump();
				get(cur[a]) = 2;
				res[a] += dcs[a][i];
				cur[a] += ds[i];

				string rr = go(cur[0], cur[1], targetSize - res[0].size() - res[1].size());
//				cout<<"eq res size: "<<res[0].size()<<' '<<res[1].size()<<' '<<rr.size()<<" ; "<<targetSize<<'\n';
				if (int(res[0].size() + res[1].size() + rr.size()) == targetSize) {
					res[0] += rr;
					reverse(res[1].begin(), res[1].end());
					return res[0] + res[1];
				}

				res[a].erase(res[a].end()-1);
				cur[a] -= ds[i];
				get(cur[a]) = 1;
			}
			goto end;
		}
	}
	for(int i=0; i<4; ++i) if (cur[1]==cur[0]+ds[i]) res[0]+=dcs[0][i];
	reverse(res[1].begin(), res[1].end());

end:
	memcpy(used, &oldUsed[0], sizeof(used));

	return res[0] + res[1];
}

int main() {
	int t;cin>>t;
	while(t--){
		int n,m,y1,x1,y2,x2;
		cin>>n>>m>>y1>>x1>>y2>>x2;
		N=n,M=m;
		memset(used,2,sizeof(used));
		for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) used[i][j] = 0;
		string res = go({x1,y1}, {x2,y2}, n*m-1);
		if ((int)res.size() == n*m-1) cout<<"YES\n"<<res<<'\n';
		else cout<<"NO\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...` view save

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

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

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

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

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

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

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

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 DDRRRUULLDR NO YES URRRDDLULDL ...` view save

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

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

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

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 LURRDDLLDRRRUUU YES RRRUUULDDLLUURD NO ...` view save

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

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

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

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