CSES - Putka Open 2020 – 4/5 - Results
Submission details
Task:Ruudukko
Sender:Olli
Submission time:2020-11-07 22:13:48 +0200
Language:C++ (C++11)
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.02 s5details
#15ACCEPTED0.01 s3, 5details
#16ACCEPTED0.04 s5details

Compiler report

input/code.cpp: In function 'std::__cxx11::string mirror(std::__cxx11::string)':
input/code.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); ++i) {
                 ~~^~~~~~~~~~
input/code.cpp: In function 'std::__cxx11::string upsidedown(std::__cxx11::string)':
input/code.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); ++i) {
                 ~~^~~~~~~~~~
input/code.cpp: In function 'std::__cxx11::string rotate(std::__cxx11::string)':
input/code.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); ++i) {
                 ~~^~~~~~~~~~
input/code.cpp: In function 'std::__cxx11::string solve(int, int, int, int, int, int)':
input/code.cpp:593:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < s.size();...

Code

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define X first
#define Y second
const int N = 55;
string mirror(string s) {
for(int i = 0; i < s.size(); ++i) {
if(s[i] == 'L') {
s[i] = 'R';
} else if (s[i] == 'R') {
s[i] = 'L';
}
}
return s;
}
string upsidedown(string s) {
for(int i = 0; i < s.size(); ++i) {
if(s[i] == 'U') {
s[i] = 'D';
} else if (s[i] == 'D') {
s[i] = 'U';
}
}
return s;
}
string reverse(string s) {
if(s.size() == 0) return "";
string t = "";
for(int i = s.size() - 1; i >= 0; --i) {
if(s[i] == 'D') {
t += 'U';
}
if(s[i] == 'U') {
t += 'D';
}
if(s[i] == 'L') {
t += 'R';
}
if(s[i] == 'R') {
t += 'L';
}
}
return t;
}
string rotate(string s) {
for(int i = 0; i < s.size(); ++i) {
if(s[i] == 'D') {
s[i] = 'L';
} else if (s[i] == 'R') {
s[i] = 'U';
} else if (s[i] == 'U') {
s[i] = 'R';
} else {
s[i] = 'D';
}
}
return s;
}
bool z[N][N];
string cur;
bool sol;
string ans;
int am;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char di[4] = {'R', 'U', 'L', 'D'};
void dfs(int h, int w, int x2, int y2, int X, int Y) {
if(sol) return;
if(z[X][Y]) return;
z[X][Y] = true;
++am;
if(am == h*w) {
ans = cur;
sol = true;
return;
}
for(int i = 0; i < 4; ++i) {
int x = X + dx[i];
int y = Y + dy[i];
if(x == x2 && y == y2 && am != h*w - 1) {
continue;
}
if(x <= 0 || x > w || y <= 0 || y > h) continue;
cur += di[i];
dfs(h, w, x2, y2, x, y);
cur.pop_back();
if(sol) break;
}
--am;
z[X][Y] = false;
}
string solveBrute(int h, int w, int x1, int y1, int x2, int y2) {
cur = "";
sol = false;
ans = "";
for(int y = 1; y <= h; ++y) {
for(int x = 1; x <= w; ++x) {
z[x][y] = false;
}
}
am = 0;
dfs(h, w, x2, y2, x1, y1);
return ans;
}
string solve(int h, int w, int x1, int y1, int x2, int y2) {
if((h*w)%2 == 0) {
if((x1 + x2 + y1 + y2)%2 == 0) return "";
} else {
if((x1 + y1)%2 == 1 || (x2 + y2)%2 == 1) return "";
}
if(h > w) {
return rotate(solve(w, h, y1, x1, y2, x2));
}
if(w <= 5 || h == 1) {
return solveBrute(h, w, x1, y1, x2, y2);
}
if(h == 2) {
if(y1 == 2) {
return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2));
}
//y1 = 1
if(x1 == x2) {
if(x1 != 1 && x1 != w) {
return "";
}
if(x1 == w) return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2));
string s = "";
for(int i = 1; i <= w-1; ++i) {
s += 'R';
}
s += 'U';
for(int i = 1; i <= w-1; ++i) {
s += 'L';
}
return s;
}
if(x2 < x1) {
return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2));
}
if(y2 == 2) {
if((x2-x1)%2 == 1) return "";
string s = "";
for(int i = 1; i <= x1 - 1; ++i) {
s += "L";
}
s += "U";
for(int i = 1; i <= x1; ++i) {
s += "R";
}
for(int i = 1; i <= (x2 - x1)/2 - 1; ++i) {
s += "DRUR";
}
s += "DR";
for(int i = 1; i <= (w - x2); ++i) {
s += "R";
}
s += "U";
for(int i = 1; i <= (w - x2); ++i) {
s += "L";
}
return s;
}
//y2 = 1
if((x2 - x1)%2 == 0) return "";
string s = "";
for(int i = 1; i <= x1 - 1; ++i) {
s += "L";
}
s += "U";
for(int i = 1; i <= x1-1; ++i) {
s += "R";
}
for(int i = 1; i <= (x2 - x1)/2; ++i) {
s += "RDRU";
}
s += "R";
for(int i = 1; i <= w - x2; ++i) {
s += "R";
}
s += "D";
for(int i = 1; i <= w - x2; ++i) {
s += "L";
}
return s;
}
if(h == 3) {
if(y1 == 3) {
return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2));
}
if(x2 < x1) {
return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2));
}
if(x2 == x1) {
if(y2 == 2) {
//y1 = 1
if(x1%2 == 1) {
return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2));
}
string s = "";
for(int i = 1; i < x1; ++i) {
s += "L";
}
s += "UU";
for(int i = 1; i < x1/2; ++i) {
s += "RDRU";
}
s += "R";
if(w == x1) {
s += "D";
return s;
}
for(int i = 1; i <= w - x1; ++i) {
s += "R";
}
s += "DD";
for(int i = 1; i <= (w - x1 - 1)/2; ++i) {
s += "LULD";
}
s += "LUL";
return s;
}
if(y1 == 2) {
return reverse(solve(h, w, x2, y2, x1, y1));
}
//y1 = 1 and y2 = 3
if(x1%2 == 0) return "";
string s = "";
for(int i = 1; i <= x1 - 1; ++i) {
s += "L";
}
s += "U";
for(int i = 1; i <= x1/2; ++i) {
s += "URDR";
}
for(int i = 1; i <= (w - x1)/2; ++i) {
s += "RDRU";
}
s += "U";
for(int i = 1; i <= (w - x1); ++i) {
s += "L";
}
return s;
}
if(w%2 == 0) {
if((x1 + y1)%2 == 1) {
if(x2 > x1 + 1) {
return "";
}
if(y1 == 2) {
return "";
}
//x2 = x1 + 1, y1 = 1
//x1%2 = 0
if(y2 == 1) {
string s = "";
for(int i = 1; i < x1; ++i) {
s += "L";
}
s += "UU";
for(int i = 1; i <= x1/2; ++i) {
s += "RDRU";
}
for(int i = 1; i <= w - x2; ++i) {
s += "R";
}
s += "DD";
for(int i = 1; i <= (w - x2)/2; ++i) {
s += "LULD";
}
s += "L";
return s;
}
if(y2 == 2) {
return "";
}
if(y2 == 3) {
string s = "";
for(int i = 1; i < x1; ++i) {
s += "L";
}
s += "UU";
for(int i = 1; i < x2/2; ++i) {
s += "RDRU";
}
s += "RDRD";
for(int i = 1; i <= w - x2; ++i) {
s += "R";
}
s += "UU";
for(int i = 1; i <= (w - x2)/2; ++i) {
s += "LDLU";
}
s += "L";
return s;
}
} else {
if(y1 == 1) {
if(y2 == 1) {
string s = "";
for(int i = 1; i < x1; ++i) {
s += "L";
}
s += "UU";
for(int i = 1; i <= x1/2; ++i) {
s += "RDRU";
}
for(int i = 1; i <= (x2 - x1)/2; ++i) {
s += "RDDRUU";
}
s += "RD";
for(int i = 1; i <= (w - x2)/2; ++i) {
s += "RURD";
}
s += "D";
for(int i = 1; i <= w - x2; ++i) {
s += "L";
}
return s;
}
if(y2 == 2) {
string s = "";
for(int i = 1; i < x1; ++i) {
s += "L";
}
s += "UU";
for(int i = 1; i <= x1/2; ++i) {
s += "RDRU";
}
for(int i = 1; i < (x2 - x1)/2; ++i) {
s += "RDDRUU";
}
s += "RDDR";
for(int i = 1; i <= w - x2; ++i) {
s += "R";
}
s += "UU";
for(int i = 1; i <= (w - x2)/2; ++i) {
s += "LDLU";
}
s += "LD";
return s;
}
string s = "";
for(int i = w - x1; i >= 1; --i) {
s += "R";
}
s += "U";
for(int i = 1; i <= (w - x2)/2; ++i) {
s += "ULDL";
}
for(int i = 1; i <= x2 - x1; ++i) {
s += "L";
}
for(int i = 1; i <= x1/2; ++i) {
s += "LDLU";
}
s += "U";
for(int i = 1; i < x2; ++i) {
s += "R";
}
return s;
} else {
//w is even
//x1 + y1 is even
//y1 is 2
if(y2 == 3) {
return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2));
}
if(y2 == 1) {
return reverse(solve(h, w, x2, y2, x1, y1));
}
//y2 = 2
string s = "";
s += "U";
for(int i = 1; i < x1/2; ++i) {
s += "LDLU";
}
s += "LDD";
for(int i = 1; i < x1; ++i) {
s += "R";
}
for(int i = 1; i <= (x2 - x1)/2; ++i) {
s += "RUURDD";
}
s += "R";
for(int i = 1; i <= (w - x2)/2; ++i) {
s += "RURD";
}
s += "RUU";
for(int i = 1; i <= w - x2; ++i) {
s += "L";
}
s += "D";
return s;
}
}
} else {
//w is odd
if(y1 == 1 && y2 == 1) {
//x1 and x2 are odd
string s = "";
for(int i = 1; i < x1; ++i) {
s += "L";
}
s += "UU";
for(int i = 1; i <= x1/2; ++i) {
s += "RDRU";
}
for(int i = 1; i <= w - x1; ++i) {
s += "R";
}
s += "D";
for(int i = 1; i <= (w - x2)/2; ++i) {
s += "DLUL";
}
for(int i = 1; i < x2 - x1; ++i) {
s += "L";
}
s += "D";
for(int i = 1; i < x2 - x1; ++i) {
s += "R";
}
return s;
}
if(y1 == 1 && y2 == 2) {
string s = "";
for(int i = 1; i < x1; ++i) {
s += "L";
}
s += "UU";
for(int i = 1; i <= x1/2; ++i) {
s += "RDRU";
}
for(int i = 1; i <= (x2 - x1)/2; ++i) {
s += "RDDRUU";
}
for(int i = 1; i <= w - x2 + 1; ++i) {
s += "R";
}
s += "D";
for(int i = 1; i <= (w - x2)/2; ++i) {
s += "DLUL";
}
s += "DLU";
return s;
}
if(y1 == 1 && y2 == 3) {
string s = "";
for(int i = 1; i < x1; ++i) {
s += "L";
}
s += "UU";
for(int i = 1; i <= x1/2; ++i) {
s += "RDRU";
}
for(int i = 1; i < (x2 - x1)/2; ++i) {
s += "RDDRUU";
}
s += "RDD";
for(int i = 1; i <= w - x2 + 1; ++i) {
s += "R";
}
s += "UU";
for(int i = 1; i <= (w - x2)/2; ++i) {
s += "LDLU";
}
return s;
}
if(y1 == 2 && y2 == 2) {
string s = "D";
for(int i = 1; i < x1; ++i) {
s += "L";
}
s += "U";
for(int i = 1; i < x1/2; ++i) {
s += "URDR";
}
s += "UR";
for(int i = 1; i < (x2 - x1)/2; ++i) {
s += "RDDRUU";
}
s += "RDDR";
for(int i = 1; i <= w - x2; ++i) {
s += "R";
}
s += "U";
for(int i = 1; i <= (w - x2)/2; ++i) {
s += "ULDL";
}
s += "ULD";
return s;
}
if(y2 == 3) {
return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2));
}
return reverse(solve(h, w, x2, y2, x1, y1));
}
}
//h >= 4
//also w >= 4
if(x2 < x1) {
return reverse(solve(h, w, x2, y2, x1, y1));
}
if(x1 >= 3) {
string s = solve(h, w-2, x1-2, y1, x2-2, y2);
int x = x1 - 2;
int y = y1;
string t = "";
bool f = true;
for(int i = 0; i < s.size(); ++i) {
if(x == 1 && s[i] != 'R' && f) {
t += 'L';
if(s[i] == 'U') {
t += solve(h, 2, 2, y, 2, y+1);
} else {
t += solve(h, 2, 2, y, 2, y-1);
}
t += 'R';
f = false;
continue;
} else {
t += s[i];
if(s[i] == 'U') {
++y;
}
if(s[i] == 'D') {
--y;
}
if(s[i] == 'L') {
--x;
}
if(s[i] == 'R') {
++x;
}
}
}
return t;
}
if(x2 <= w - 2) {
string s = solve(h, w-2, x1, y1, x2, y2);
int x = x1;
int y = y1;
string t = "";
bool f = true;
for(int i = 0; i < s.size(); ++i) {
if(x == w - 2 && s[i] != 'L' && f) {
t += 'R';
if(s[i] == 'U') {
t += solve(h, 2, 1, y, 1, y+1);
} else {
t += solve(h, 2, 1, y, 1, y-1);
}
t += 'L';
f = false;
continue;
} else {
t += s[i];
if(s[i] == 'U') {
++y;
}
if(s[i] == 'D') {
--y;
}
if(s[i] == 'L') {
--x;
}
if(s[i] == 'R') {
++x;
}
}
}
return t;
}
//x1 = 1 or 2, x2 = w or w-1
int a = -1;
string A = "";
for(int i = 1; i <= h; ++i) {
A = solve(h, 2, x1, y1, 2, i);
if(A.size() != 0) {
a = i;
break;
}
}
A += "R";
A += solve(h, w-2, 1, a, x2-2, y2);
return A;
}
int main() {
int t;
cin >> t;
while(t > 0) {
--t;
int h, w, x1, y1, x2, y2;
cin >> h >> w >> y1 >> x1 >> y2 >> x2;
y1 = h+1 - y1; y2 = h+1 - y2;
string s = solve(h, w, x1, y1, x2, y2);
if(s.size() == 0) {
cout << "NO\n";
} else {
cout << "YES\n";
cout << s << "\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
...

correct output
YES
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...

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

correct output
NO
NO
NO
NO
YES
...

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

correct output
NO
NO
NO
YES
RRRRRRRUULDLULDLULDLLUR
...

user output
NO
NO
NO
YES
RRRRRRRUULDLULDLULDLLUR
...
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
...

correct output
YES
DDRRRRRRULLLLLURRRRRULLLLLLLDD...

user output
YES
ULLLLDRDRURDRRUURDDRUURDDRUURD...
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
...

correct output
NO
YES
LURULURULURULURULURRDDDDDDDDDR...

user output
NO
YES
RRDDDDLLLUURDRUULLULLLLLLUUUUL...
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
...

correct output
YES
LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL...

user output
YES
LDRDLDRRUUUULLLDDDDLUUUULDDDDD...
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
...

correct output
YES
LLDRRRU
NO
NO
NO
...

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

correct output
YES
LDRRURRDL
YES
RRRDLLLLU
NO
...

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

correct output
YES
DDRRRUULLDR
NO
YES
URRRDDLULDL
...

user output
YES
RRRDDLLLURR
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
...

correct output
NO
NO
YES
UURRRRDDLULDLU
NO
...

user output
NO
NO
YES
RRRRUULDLULLDR
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
...

correct output
NO
NO
NO
YES
LLLDRRRRURDRUULLLLLLLDD
...

user output
NO
NO
NO
YES
URDRURDDLLLLUULDDLUULDD
...
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
...

correct output
NO
NO
NO
NO
NO
...

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

correct output
YES
DDLUUURRDDDRUUU
YES
UUURRRDLDRDLLUU
NO
...

user output
YES
RRDDLULDLUUURRR
YES
RRRUUULLLDDRRUL
NO
...
Truncated

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

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

correct output
YES
DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU...

user output
YES
DDDDDDDDDDDDDDDDDDDDDRRRRRRRRR...
Truncated