— Dark mode

Putka Open 2020 – 4/5

Ruudukko

  • Start: 2020-11-06 18:00:00
  • End: 2020-11-08 23:00:00
CSES - Putka Open 2020 – 4/5 - Results
Submission details
Task:Ruudukko
Sender:Sisuaski
Submission time:2020-11-08 10:55:32 +0200
Language:C++ (C++17)
Status:READY
Result:17
Feedback
groupverdictscore
#1ACCEPTED5
#2ACCEPTED12
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 5details
#2ACCEPTED0.01 s2, 5details
#3ACCEPTED0.01 s3, 5details
#40.01 s4, 5details
#50.02 s5details
#60.02 s5details
#7ACCEPTED0.01 s2, 5details
#8ACCEPTED0.01 s2, 5details
#9ACCEPTED0.01 s3, 5details
#10ACCEPTED0.01 s3, 5details
#110.01 s3, 5details
#12ACCEPTED0.01 s3, 5details
#130.01 s4, 5details
#140.01 s5details
#150.01 s3, 5details
#16ACCEPTED0.04 s5details

Code

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

char used[64][64];

C ds[] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
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 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();
}

string go(C from, C to, int targetSize) {
	string oldUsed(&used[0][0], sizeof(used));

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

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

			if (cnts[a] == 2 &&
					((!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;
					cur[a] += ds[i];
					res[a] += dcs[a][i];

//					cout<<"forking...\n";
					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];
				}
				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) ba=a,bi=i,best=val;
			}
		}
		if (ba<0) break;
		res[ba] += dcs[ba][bi];
		get(cur[ba]) = 2;
		cur[ba] += ds[bi];
	}
	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());

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

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

Test 5

Group: 5

Verdict:

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

Test 6

Group: 5

Verdict:

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

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

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

Test 14

Group: 5

Verdict:

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

Test 15

Group: 3, 5

Verdict:

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

Tasks

A Neliöt-B Peli-C Tekijät-D Ruudukko-

Submissions (Sisuaski)

2020-11-08 17:28:12 1002020-11-08 16:56:19 722020-11-08 16:54:23 722020-11-08 13:49:33 722020-11-08 12:42:12 52020-11-08 11:40:06 722020-11-08 11:30:19 442020-11-08 10:55:32 172020-11-08 09:19:24 172020-11-08 08:32:53 172020-11-08 08:31:34 02020-11-07 20:37:50 172020-11-07 20:33:50 5