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

board

// 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);
      |         ^~~~~

Subtask #1
10.0 / 10.0

#	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

Subtask #2
10.0 / 10.0

#	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

Subtask #3
10.0 / 10.0

#	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

Subtask #4
10.0 / 10.0

#	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

Subtask #5
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #6
10.0 / 10.0

#	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

Subtask #7
10.0 / 10.0

#	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

Subtask #8
10.0 / 10.0

#	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

Subtask #9
10.0 / 10.0

#	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

Subtask #10
10.0 / 10.0

#	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