Submission #782909

# Submission time Handle Problem Language Result Execution time Memory
782909 2023-07-14T11:25:20 Z RecursiveCo Board (CEOI13_board) C++14
100 / 100
5 ms 2268 KB
// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

#define int long long

vector<int> compress(string s) {
    stack<pair<int, int>> sst;
    int n = s.size();
    int len, el, lenbefore, bfbf;
    forto(n, i) {
        switch (s[i]) {
            case '1':
                if (sst.empty() || sst.top().first == 2) sst.push({1, 1});
                else {
                    len = sst.top().second;
                    sst.pop();
                    sst.push({1, len + 1});
                }
                break;
            case '2':
                if (sst.empty() || sst.top().first == 1) sst.push({2, 1});
                else {
                    len = sst.top().second;
                    sst.pop();
                    sst.push({2, len + 1});
                }
                break;
            case 'U':
                len = sst.top().second;
                el = sst.top().first;
                sst.pop();
                if (len != 1) sst.push({el, len - 1});
                break;
            case 'L':
                el = sst.top().first;
                len = sst.top().second;
                if (el == 2) {
                    sst.pop();
                    if (len != 1) {
                        sst.push({2, len - 1});
                        sst.push({1, 1});
                    } else {
                        if (sst.empty()) {
                            sst.push({1, 1});
                        } else {
                            lenbefore = sst.top().second;
                            sst.pop();
                            sst.push({1, lenbefore + 1});
                        }
                    }
                } else {
                    sst.pop();
                    lenbefore = sst.top().second;
                    if (lenbefore != 1) {
                        sst.pop();
                        sst.push({2, lenbefore - 1});
                        sst.push({1, 1});
                        sst.push({2, len});
                    } else {
                        sst.pop();
                        if (sst.empty()) {
                            sst.push({1, 1});
                            sst.push({2, len});
                        } else {
                            bfbf = sst.top().second;
                            sst.pop();
                            sst.push({1, bfbf + 1});
                            sst.push({2, len});
                        }
                    }
                }
                break;
            case 'R':
                el = sst.top().first;
                len = sst.top().second;
                if (el == 1) {
                    sst.pop();
                    if (len != 1) {
                        sst.push({1, len - 1});
                        sst.push({2, 1});
                    } else {
                        if (sst.empty()) {
                            sst.push({2, 1});
                        } else {
                            lenbefore = sst.top().second;
                            sst.pop();
                            sst.push({2, lenbefore + 1});
                        }
                    }
                } else {
                    sst.pop();
                    lenbefore = sst.top().second;
                    if (lenbefore != 1) {
                        sst.pop();
                        sst.push({1, lenbefore - 1});
                        sst.push({2, 1});
                        sst.push({1, len});
                    } else {
                        sst.pop();
                        if (sst.empty()) {
                            sst.push({2, 1});
                            sst.push({1, len});
                        } else {
                            bfbf = sst.top().second;
                            sst.pop();
                            sst.push({2, bfbf + 1});
                            sst.push({1, len});
                        }
                    }
                }
                break;
        }
    }
    vector<int> res;
    while (!sst.empty()) {
        int ele = sst.top().first;
        int leng = sst.top().second;
        forto(leng, i) res.push_back(ele);
        sst.pop();
    }
    rev(res);
    return res;
}

signed main() {
    improvePerformance;
    //getTest;

    //eachTest {
        string s, t;
        cin >> s;
        cin >> t;
        vector<int> S = compress(s);
        vector<int> T = compress(t);
        if (S > T) swap(S, T);
        int slev = S.size();
        int tlev = T.size();
        vector<int> moves;
        int cnt = 0;
        forto(min(slev, tlev), i) {
            if (S[i] == T[i]) cnt *= 2;
            else if (S[i] == 1) cnt = cnt * 2 + 1;
            else cnt = cnt * 2 - 1;
            if (cnt > 250000) break;
            moves.push_back(cnt);
        }
        int ans = slev + tlev;
        forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
        out(ans);
    //}
}

Compilation message

board.cpp: In function 'std::vector<long long int> compress(std::string)':
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:24:5: note: in expansion of macro 'forto'
   24 |     forto(n, i) {
      |     ^~~~~
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:132:9: note: in expansion of macro 'forto'
  132 |         forto(leng, i) res.push_back(ele);
      |         ^~~~~
board.cpp: In function 'int main()':
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:154:9: note: in expansion of macro 'forto'
  154 |         forto(min(slev, tlev), i) {
      |         ^~~~~
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:162:9: note: in expansion of macro 'forto'
  162 |         forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
      |         ^~~~~
board.cpp:15:52: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                              ~~~~~~^~~~~~~~
board.cpp:162:9: note: in expansion of macro 'forto'
  162 |         forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
      |         ^~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 4 ms 636 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 252 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 596 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 1740 KB Output is correct
2 Correct 5 ms 1868 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 1652 KB Output is correct
2 Correct 5 ms 1740 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 5 ms 2268 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 1740 KB Output is correct
2 Correct 5 ms 1868 KB Output is correct
3 Correct 4 ms 2120 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 720 KB Output is correct
6 Correct 4 ms 2240 KB Output is correct