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

Compiler report

input/code.cpp: In function 'bool valid(std::string, int, int, std::pair<int, int>, std::pair<int, int>)':
input/code.cpp:94:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     if (res.size() != n * m - 1) return false;
      |         ~~~~~~~~~~~^~~~~~~~~~~~

Code

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007
#define N (1 << 18)

#define y first
#define x second

using namespace std;

namespace mango {
    string rev(string str) {
        for (auto& c : str) {
            if (c == 'L') c = 'R';
            else if (c == 'R') c = 'L';
            else if (c == 'D') c = 'U';
            else c = 'D';
        }
        reverse(str.begin(), str.end());
        return str;
    }

    string fix(string str) {
        for (auto& c : str) {
            if (c == 'U') c = 'D';
            else if (c == 'D') c = 'U';
        }
        return str;
    }
    
    string solveSmall(int h, int w, int y0, int x0, int y1, int x1) {
        if (x0 > x1 || (x0 == x1 && y0 > y1)) return rev(solveSmall(h, w, y1, x1, y0, x0));
    
        if (h == 1) {
            if (x0 == 0 && x1 == w-1) return string(w-1, 'R');
            if (x0 == w-1 && x1 == 0) return string(w-1, 'L');
            return "";
        } else {
            if (x0 == x1 && 0 < x0 && x0 < w-1) return "";
    
            string res;
            if (x0 == x1 && x0 == 0) {
                for (int i = 0; i < w-1; ++i) res.push_back('R');
    
                if (y0 == 0) res.push_back('U');
                else res.push_back('D');
    
                for (int i = 0; i < w-1; ++i) res.push_back('L');
    
            } else {
                for (int i = 0; i < x0; ++i) res.push_back('L');
    
                if (y0 == 0) res.push_back('U');
                else res.push_back('D');
    
                for (int i = 0; i < x0; ++i) res.push_back('R');
    
                if (x0 == x1) return res;
    
                for (int i = 0; i < x1 - x0 - 1; ++i) {
                    res.push_back('R');
                    if ((i ^ y0) & 1) res.push_back('U');
                    else res.push_back('D');
                }
                res.push_back('R');
    
                for (int i = 0; i < w-1 - x1; ++i) res.push_back('R');
    
                if (y1 == 0) res.push_back('D');
                else res.push_back('U');
    
                for (int i = 0; i < w-1 - x1; ++i) res.push_back('L');
            }
            
            return res;
        }
    }

    string solve2(int n, int m, pair<int, int> s, pair<int, int> t) {
        return fix(solveSmall(n, m, s.y - 1, s.x - 1, t.y - 1, t.x - 1));
    }
};

bool valid(string res, int n, int m, pair<int, int> s, pair<int, int> t) {
    map<char, pair<int, int>> dir_to_dif;
    dir_to_dif['U'] = {-1, 0};
    dir_to_dif['D'] = {1, 0};
    dir_to_dif['R'] = {0, 1};
    dir_to_dif['L'] = {0, -1};
    map<pair<int, int>, bool> mp;

    if (res.size() != n * m - 1) return false;

    int idx = 0;

    while (s != t) {
        if (mp[s] == 1) {
            return false;
        }
        mp[s] = 1;

        char c = res[idx++];
        s.y += dir_to_dif[c].y;
        s.x += dir_to_dif[c].x;

        if (s.y <= 0 || s.y > n || s.x <= 0 || s.x > m) return false;
    }

    return true;
}

bool check_small(int h, int w, int y0, int x0, int y1, int x1) {
	if (x0 > x1 || (x0 == x1 && y0 > y1)) return check_small(h, w, y1, x1, y0, x0);
 
	if (h == 1) {
		if (x0 == 0 && x1 == w-1) return true;
		if (x0 == w-1 && x1 == 0) return true;
		return false;
	} else {
		if (x0 == x1 && 0 < x0 && x0 < w-1) return false;
		return true;
	}
}

bool works(int h, int w, int y0, int x0, int y1, int x1) {
	if (y0 == y1 && x0 == x1) return false;
	if (w < h) return works(w, h, x0, y0, x1, y1);
	if (! ((h*w ^ abs(x0 - x1) ^ abs(y0 - y1)) & 1)) return false;
	if ((h*w & 1) && ((x0 + y0) & 1)) return false;
 
	if (h <= 2) return check_small(h, w, y0, x0, y1, x1);
	if (h == 3 && (!(w & 1))) {
		if (y0 == 1) {
			if ((x0 & 1) && x1 < x0) return false;
			if (!(x0 & 1) && x1 > x0) return false;
		} else {
			if (!(x0 & 1) && (x1 < x0 - 1)) return false;
			if ((x0 & 1) && (x1 > x0 + 1)) return false;
		}
	}   
	return true;
}

bool inside(int n, int m, pair<int, int> p) {
    return p.x <= m && p.y <= n && p.x > 0 && p.y > 0;
}

bool ok(int h, int w, pair<int, int> s, pair<int, int> t) {
    if (h == 0) return s.x == t.x;
    return works(h, w, s.y - 1, s.x - 1, t.y - 1, t.x - 1);
}

pair<int, int> offset(pair<int, int> p, pair<int, int> off) {
    return {p.y + off.y, p.x + off.x};
}

const int cutoff = 20;

string rev(string s) {
    map<char, char> sw;
    sw['U'] = 'D';
    sw['D'] = 'U';
    sw['L'] = 'R';
    sw['R'] = 'L';

    string ans;
    for (char c : s) ans += sw[c];
    reverse(ans.begin(), ans.end());
    return ans;
}

bool vis[51][51];

string run_brute(int n, int m, pair<int, int> c, pair<int, int> t, int left) {
    if (c.x < 1 || c.x > m || c.y < 1 || c.y > n) return "X";
    if (vis[c.y][c.x]) return "X";
    if (left == 0) {
        return c == t ? "" : "X";
    }

    vis[c.y][c.x] = 1;

    string p = run_brute(n, m, {c.y - 1, c.x}, t, left - 1);
    if (p != "X") return "U" + p;

    p = run_brute(n, m, {c.y + 1, c.x}, t, left - 1);
    if (p != "X") return "D" + p;

    p = run_brute(n, m, {c.y, c.x - 1}, t, left - 1);
    if (p != "X") return "L" + p;

    p = run_brute(n, m, {c.y, c.x + 1}, t, left - 1);
    if (p != "X") return "R" + p;

    vis[c.y][c.x] = 0;
    return "X";
}

string brute(int n, int m, pair<int, int> s, pair<int, int> t) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) vis[i][j] = 0;
    }

    return run_brute(n, m, s, t, n * m - 1);
}

string c2(int n, int m, pair<int, int> s, pair<int, int> t, int times) {
    pair<int, int> dif = {s.y - t.y, s.x - t.x};

    string ans_first;
    string ans_mid;
    string ans_second;

    if (dif == make_pair(0, -1)) {
        ans_first += string(s.x - 1, 'L');
        ans_first += s.y == 2 ? "U" : "D";
        ans_first += string(s.x - 1, 'R');
        ans_first += s.y == 2 ? "U" : "D";

        ans_mid = "R";

        ans_second += string(m - t.x, 'R');
        ans_second += s.y == 2 ? "D" : "U";
        ans_second += string(m - t.x, 'L');
        ans_second += s.y == 2 ? "D" : "U";
    }
    if (dif == make_pair(0, 1)) {
        ans_first += string(m - s.x, 'R');
        ans_first += s.y == 2 ? "U" : "D";
        ans_first += string(m - s.x, 'L');
        ans_first += s.y == 2 ? "U" : "D";

        ans_mid = "L";

        ans_second += string(t.x - 1, 'L');
        ans_second += s.y == 2 ? "D" : "U";
        ans_second += string(t.x - 1, 'R');
        ans_second += s.y == 2 ? "D" : "U";
    }
    if (dif == make_pair(-1, 0)) {
        ans_first += string(s.y - 1, 'U');
        ans_first += s.x == 2 ? "L" : "R";
        ans_first += string(s.y - 1, 'D');
        ans_first += s.x == 2 ? "L" : "R";

        ans_mid = "D";

        ans_second += string(n - t.y, 'D');
        ans_second += s.x == 2 ? "R" : "L";
        ans_second += string(n - t.y, 'U');
        ans_second += s.x == 2 ? "R" : "L";
    }
    if (dif == make_pair(1, 0)) {
        ans_first += string(n - s.y, 'D');
        ans_first += s.x == 2 ? "L" : "R";
        ans_first += string(n - s.y, 'U');
        ans_first += s.x == 2 ? "L" : "R";

        ans_mid = "U";

        ans_second += string(t.y - 1, 'U');
        ans_second += s.x == 2 ? "R" : "L";
        ans_second += string(t.y - 1, 'D');
        ans_second += s.x == 2 ? "R" : "L";
    }

    string ans;

    for (int i = 0; i < times; ++i) ans += ans_first;
    ans.pop_back();
    ans += ans_mid;
    for (int i = 0; i < times; ++i) ans += ans_second;
    ans.pop_back();

    return ans;
}

string solve_strip(tuple<int, int, pair<int, int>, pair<int, int>> p1, string path, pair<int, int> pos, int times) {
    map<char, pair<int, int>> dir_to_dif;
    dir_to_dif['U'] = {-1, 0};
    dir_to_dif['D'] = {1, 0};
    dir_to_dif['R'] = {0, 1};
    dir_to_dif['L'] = {0, -1};

    string res;

    pair<int, int> tgt = get<2>(p1);

    if (pos.x == tgt.x || pos.y == tgt.y) {
        bool begin = 0;
        if (get<3>(p1).y == 1 && path[0] == 'D') {
            begin = 1;
        } else if (get<3>(p1).y > 1 && path[0] == 'U') {
            begin = 1;
        } else if (get<3>(p1).x == 1 && path[0] == 'R') {
            begin = 1;
        } else if (get<3>(p1).x > 1 && path[0] == 'L') {
            begin = 1;
        }

        if (begin) {
            pair<int, int> dif = dir_to_dif[path[res.size()]];
            pos = make_pair(pos.y + dif.y, pos.x + dif.x);
            res += (path[res.size()]);
        }
    }

    while (pos.x != tgt.x && pos.y != tgt.y) {
        pair<int, int> dif = dir_to_dif[path[res.size()]];
        pos = make_pair(pos.y + dif.y, pos.x + dif.x);
        res += (path[res.size()]);
    }

    string end_path = path.size() > res.size() + 1 ? path.substr(res.size() + 1, 1e5) : "";

    if (get<3>(p1).y == 1) {
        res = res + "U" + c2(2, get<1>(p1), {2, pos.x}, {2, pos.x + dir_to_dif[path[res.size()]].x}, times) + "D";
    } else if (get<3>(p1).y > 1) {
        res = res + "D" + c2(2, get<1>(p1), {1, pos.x}, {1, pos.x + dir_to_dif[path[res.size()]].x}, times) + "U";
    } else if (get<3>(p1).x == 1) {
        res = res + "L" + c2(get<0>(p1), 2, {pos.y, 2}, {pos.y + dir_to_dif[path[res.size()]].y, 2}, times) + "R";
    } else if (get<3>(p1).x > 1) {
        res = res + "R" + c2(get<0>(p1), 2, {pos.y, 1}, {pos.y + dir_to_dif[path[res.size()]].y, 1}, times) + "L";
    }

    return res + end_path;
}

string solve_m(int n, int m, pair<int, int> s, pair<int, int> t) {  
    if (s.x > t.x) return rev(solve_m(n, m, t, s));
    int min_j = min(s.x, t.x);
    int max_j = max(s.x, t.x);

    for (int j = min_j - min_j % 2; j > 0; j -= 2) {
        if (min_j > j) {
            if (ok(n, m - j, offset(s, {0, -j}), offset(t, {0, -j}))) {
                auto x1 = make_tuple(n, 2, make_pair(0, 1), make_pair(0,1));
                string path = solve_m(n, m - j, offset(s, {0, -j}), offset(t, {0, -j}));

                return solve_strip(x1, path, offset(s, {0, -j}), j / 2);
            }
        }
    }
    
    for (int j = (m - max_j) / 2 * 2; j > 0; j -= 2) {
        if (max_j <= m - j) {
            if (ok(n, m - j, s, t)) {
                auto x1 = make_tuple(n, 2, make_pair(0, m - j), make_pair(0,2));
                string path = solve_m(n, m - j, s, t);

                return solve_strip(x1, path, s, j / 2);
            }
        }
    }
    

    set<int> st_i;
    st_i.insert(1);
    st_i.insert(2);
    
    if (n % 2 == 0) st_i.insert(n);
    else st_i.insert(n - 1);
    for (int i : st_i) {
        int first_m = 2;
        int second_m = m - 2;

        pair<int, int> first_e = {i, first_m};
        pair<int, int> second_e = {i, first_m + 1};

        if (inside(n, first_m, s) 
            && inside(n, second_m, offset(t, {0, -first_m}))
            && ok(n, first_m, s, first_e) 
            && ok(n, second_m, offset(t, {0, -first_m}), offset(second_e, {0, -first_m}))
        ) { 
            string s1 = solve_m(n, first_m, s, first_e);
            string s2 = solve_m(n, second_m, offset(second_e, {0, -first_m}), offset(t, {0, -first_m}));

            return s1 + "R" + s2;
        }
    }

    return brute(n, m, s, t);
}

string solve_mid(int n, int m, int j1, int j2) {
    string res;

    int orig = n;
    int origj1 = j1;

    while (n > 2) {
        if (n * m <= cutoff) {
            res += brute(n, m, {1, j1}, {n, j2});
            return res;
        }
        for (int j = 1; j <= m; ++j) {
            if (ok(2, m, {1, j1}, {2, j})
                && ok(n - 2, m, {1, j}, {2, j2})) {
                res += mango::solve2(2, m, {1, j1}, {2, j});
                j1 = j; 
                break;
            }
        }

        res += "D";
        n -= 2;
    }

    res += mango::solve2(2, m, {1, j1}, {2, j2});

    if (!valid(res, orig, m, {1, origj1}, {orig, j2})) {
        cout << orig << " " << m << " " << origj1 << " " << j2 << " " << res.size() << endl;
        exit(-1);
    }

    return res;
}

string solve(int n, int m, pair<int, int> s, pair<int, int> t) {
    int min_i = min(s.y, t.y);
    int max_i = max(s.y, t.y);

    //cout << n << " " << m << " " << min_i << " " << max_i << endl;

    for (int i = min_i - min_i % 2; i > 0; i -= 2) {
        if (min_i > i) {
            if (ok(n - i, m, offset(s, {-i, 0}), offset(t, {-i, 0}))) {
                auto x1 = make_tuple(2, m, make_pair(1, 0), make_pair(1,0));
                string path = solve(n - i, m, offset(s, {-i, 0}), offset(t, {-i, 0}));

                return solve_strip(x1, path, offset(s, {-i, 0}), i / 2);
            }
        }
    }

    for (int i = (n - max_i) / 2 * 2; i > 0; i -= 2) {
        if (max_i <= n - i) {
            if (ok(n - i, m, s, t)) {
                //cout << i << " " << n << " " << max_i << endl;
                auto x1 = make_tuple(2, m, make_pair(n - i, 0), make_pair(2,0));

                string path = solve(n - i, m, s, t);

                return solve_strip(x1, path, s, i / 2);
            }
        }
    }

    if (n <= 3 || max_i <= 2 || min_i > 2) {
        return solve_m(n, m, s, t);
    }

    // Assume s.y <= 2 and t.y >= n - 1

    int left_n = 2;
    int right_n = 2 + (n % 2);

    int mid = n - left_n - right_n;

    for (int j1 = 1; j1 <= m; ++j1) {
        for (int j2 = 1; j2 <= m; ++j2) {
            pair<int, int> first_e = {left_n, j1};
            pair<int, int> second_e = {1, j2};

            if (ok(left_n, m, s, first_e) 
                && ok(right_n, m, second_e, offset(t, {-(left_n + mid), 0}))
                && ok(mid, m, {1, j1}, {mid, j2})) {
                
                string ans = mango::solve2(left_n, m, s, first_e);
                if (mid != 0) ans += "D" + solve_mid(mid, m, j1, j2);
                // if (mid != 0) ans += "D" + solve(mid, m, {1, j1}, {mid, j2});
                ans += "D" + solve_m(right_n, m, second_e, offset(t, {-(left_n + mid), 0}));

                return ans;
            }
        }
    }

    return solve_m(n, m, s, t);
}

void test_case() {
    int n, m;
    pair<int, int> s, t;

    cin >> n >> m >> s.y >> s.x >> t.y >> t.x;

    if (!ok(n, m, s, t)) {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
    //cout << n << " " << m << " " << s.y << " " << s.x << " " << t.y << " " << t.x << endl;
    string ans = s <= t ? solve(n, m, s, t) : rev(solve(n, m, t, s));
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        test_case();
    }

    return 0;
}

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

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

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

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

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

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
UURRRRDDLULDLU
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
LURRDDLLDRRRUUU
YES
RRRULLLUURRRDLL
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
RRRRRULLLLLLDLULDLULDLULDLULDL...

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