Submission #38710

#	Time	Username	Problem	Language	Result	Execution time	Memory
38710		aome	Board (CEOI13_board)	C++14	100 / 100	3 ms	2704 KiB

board

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, char> ic;

void modify(string &S, vector<char> &V) {
    stack<ic> st;
    for (int i = 0; i < S.size(); ++i) {
        if (S[i] == '1' || S[i] == '2') {
            if (!st.size() || st.top().second != S[i]) {
                st.push(ic(1, S[i]));
            }
            else st.top().first++;
        }
        if (S[i] == 'U') {
            st.top().first--;
            if (st.top().first == 0) st.pop();
        }
        if (S[i] == 'L') {
            ic tmp;
            bool flag = 0;
            if (st.top().second == '1') {
                flag = 1, tmp = st.top(), tmp.second = '2', st.pop();
            }
            st.top().first--;
            if (!st.top().first) {
                st.pop();
                if (st.size()) st.top().first++;
                else st.push(ic(1, '1'));
            }
            else st.push(ic(1, '1'));
            if (flag) st.push(tmp);
        }
        if (S[i] == 'R') {
            ic tmp;
            bool flag = 0;
            if (st.top().second == '2') {
                flag = 1, tmp = st.top(), tmp.second = '1', st.pop();
            }
            st.top().first--;
            if (!st.top().first) {
                st.pop();
                if (st.size()) st.top().first++;
                else st.push(ic(1, '2'));
            }
            else st.push(ic(1, '2'));
            if (flag) st.push(tmp);
        }
    }
    while (st.size()) {
        ic tmp = st.top(); st.pop();
        while (tmp.first--) V.push_back(tmp.second);
    }
    reverse(V.begin(), V.end());
}

void print(vector<char> &V) {
    for (int i = 0; i < V.size(); ++i) cout << V[i]; cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    string sA, sB; cin >> sA >> sB;
    vector<char> vA, vB;
    modify(sA, vA), modify(sB, vB);
//    print(vA), print(vB);
    int res = 1e9, dis = 0;
    int szA = vA.size(), szB = vB.size();
    for (int i = 0; i < min(szA, szB); ++i) {
        res = min(res, szA + szB - 2 * i + dis);
        if (!dis) {
            if (vA[i] == vB[i]) continue;
            else {
                dis = 1;
                if (vA[i] == '2') swap(vA, vB), swap(szA, szB);
            }
        }
        else {
            if (vA[i] == '2' && vB[i] == '1') dis = dis * 2 - 1;
            else if (vA[i] == '1' && vB[i] == '2') dis = dis * 2 + 1;
            else dis = dis * 2;
        }
        if (dis > res) break;
    }
    res = min(res, szA + szB - 2 * min(szA, szB) + dis);
    cout << res;
}

Compilation message (stderr)

board.cpp: In function 'void modify(std::__cxx11::string&, std::vector<char>&)':
board.cpp:8:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < S.size(); ++i) {
                       ^
board.cpp: In function 'void print(std::vector<char>&)':
board.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < V.size(); ++i) cout << V[i]; cout << '\n';
                       ^

• 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: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10