— 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 08:31:34 +0200
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.01 s1, 5details
#20.01 s2, 5details
#30.02 s3, 5details
#40.02 s4, 5details
#50.11 s5details
#60.12 s5details
#70.01 s2, 5details
#80.01 s2, 5details
#90.01 s3, 5details
#100.01 s3, 5details
#110.01 s3, 5details
#120.01 s3, 5details
#130.01 s4, 5details
#140.10 s5details
#150.02 s3, 5details
#160.42 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);
	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) {
	string res[2];
	C cur[2] = {from, to};
	while(cur[0] != cur[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;
			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);
				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());
	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});
		if ((int)res.size() == n*m-1) cout<<"YES\n"<<res<<'\n';
		else cout<<"NO\n";
	}
}

Test details

Test 1

Group: 1, 5

Verdict:

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
cur (45,1) (1,1)
cur (44,1) (1,1)
cur (43,1) (1,1)
cur (42,1) (1,1)
cur (41,1) (1,1)
...
Truncated

Test 2

Group: 2, 5

Verdict:

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
cur (33,1) (21,1)
cur (34,1) (21,1)
cur (35,1) (21,1)
cur (36,1) (21,1)
cur (37,1) (21,1)
...
Truncated

Test 3

Group: 3, 5

Verdict:

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
cur (1,2) (4,2)
cur (1,3) (4,2)
cur (2,3) (4,2)
cur (2,2) (4,2)
cur (3,2) (4,2)
...
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
cur (19,2) (5,1)
cur (19,2) (4,1)
cur (19,2) (3,1)
cur (19,2) (2,1)
cur (19,2) (1,1)
...
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
cur (1,13) (8,14)
cur (1,12) (8,14)
cur (1,11) (8,14)
cur (1,10) (8,14)
cur (1,9) (8,14)
...
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
cur (35,18) (37,31)
cur (35,18) (38,31)
cur (35,18) (38,30)
cur (35,18) (37,30)
cur (35,18
...
Truncated

Test 7

Group: 2, 5

Verdict:

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
cur (3,1) (4,1)
cur (3,1) (4,2)
cur (3,1) (3,2)
cur (2,1) (3,2)
cur (2,1) (2,2)
...
Truncated

Test 8

Group: 2, 5

Verdict:

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
cur (2,1) (4,2)
cur (1,1) (4,2)
cur (1,2) (4,2)
cur (2,2) (4,2)
cur (3,2) (4,2)
...
Truncated

Test 9

Group: 3, 5

Verdict:

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
cur (1,1) (3,2)
cur (1,2) (3,2)
cur (1,3) (3,2)
cur (2,3) (3,2)
cur (3,3) (3,2)
...
Truncated

Test 10

Group: 3, 5

Verdict:

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
cur (4,3) (2,3)
cur (5,3) (2,3)
cur (5,2) (2,3)
cur (5,1) (2,3)
cur (4,1) (2,3)
...
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
cur (8,2) (2,1)
cur (8,2) (1,1)
cur (8,2) (1,2)
cur (8,2) (1,3)
cur (8,2) (2,3)
...
Truncated

Test 12

Group: 3, 5

Verdict:

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
cur (3,1) (9,2)
cur (3,1) (9,3)
cur (3,1) (8,3)
cur (3,1) (8,2)
cur (3,1) (7,2)
...
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
cur (2,2) (4,1)
cur (2,2) (4,2)
cur (2,2) (4,3)
cur (2,2) (4,4)
cur (2,2) (3,4)
...
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
cur (22,6) (8,1)
cur (22,6) (7,1)
cur (22,6) (6,1)
cur (22,6) (5,1)
cur (22,6) (4,1)
...
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
cur (5,3) (4,1)
cur (6,3) (4,1)
cur (7,3) (4,1)
cur (8,3) (4,1)
cur (9,3) (4,1)
...
Truncated

Test 16

Group: 5

Verdict:

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
cur (1,29) (21,16)
cur (1,30) (21,16)
cur (1,31) (21,16)
cur (1,32) (21,16)
cur (1,33) (21
...
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