Submission #782878

#	Time	Username	Problem	Language	Result	Execution time	Memory
782878		RecursiveCo	Board (CEOI13_board)	C++14	70 / 100	1077 ms	1044 KiB

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<int> tobepush;
    stack<int> sst;
    int n = s.size();
    forto(n, i) {
        switch (s[i]) {
            case 'U':
                sst.pop();
                break;
            case '1':
                sst.push(1);
                break;
            case '2':
                sst.push(2);
                break;
            case 'L':
                while (1) {
                    int op = sst.top();
                    sst.pop();
                    tobepush.push(op == 1? 2: 1);
                    if (op == 2) break;
                }
                while (!tobepush.empty()) {
                    sst.push(tobepush.top());
                    tobepush.pop();
                }
                break;
            case 'R':
                while (1) {
                    int op = sst.top();
                    sst.pop();
                    tobepush.push(op == 1? 2: 1);
                    if (op == 1) break;
                }
                while (!tobepush.empty()) {
                    sst.push(tobepush.top());
                    tobepush.pop();
                }
                break;
        }
    }
    vector<int> res;
    while (!sst.empty()) res.push_back(sst.top()), 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 (stderr)

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: 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:82:9: note: in expansion of macro 'forto'
   82 |         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:90:9: note: in expansion of macro 'forto'
   90 |         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:90:9: note: in expansion of macro 'forto'
   90 |         forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
      |         ^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10