oj.uz

Submission #38710

# Submission time Handle Problem Language Result Execution time Memory
38710 2018-01-06T09:40:29 Z aome Board (CEOI13_board) C++14
100 / 100
 3 ms 2704 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2180 KB Output is correct
2 Correct 0 ms 2180 KB Output is correct
3 Correct 0 ms 2180 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2500 KB Output is correct
2 Correct 0 ms 2180 KB Output is correct
3 Correct 0 ms 2544 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2180 KB Output is correct
2 Correct 0 ms 2180 KB Output is correct
3 Correct 0 ms 2180 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2312 KB Output is correct
2 Correct 3 ms 2580 KB Output is correct
3 Correct 0 ms 2332 KB Output is correct
4 Correct 0 ms 2180 KB Output is correct
5 Correct 0 ms 2180 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2180 KB Output is correct
2 Correct 0 ms 2180 KB Output is correct
3 Correct 0 ms 2180 KB Output is correct
4 Correct 0 ms 2180 KB Output is correct
5 Correct 0 ms 2180 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2180 KB Output is correct
2 Correct 0 ms 2180 KB Output is correct
3 Correct 0 ms 2180 KB Output is correct
4 Correct 0 ms 2180 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2332 KB Output is correct
2 Correct 3 ms 2564 KB Output is correct
3 Correct 3 ms 2332 KB Output is correct
4 Correct 0 ms 2180 KB Output is correct
5 Correct 0 ms 2180 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2704 KB Output is correct
2 Correct 3 ms 2560 KB Output is correct
3 Correct 0 ms 2180 KB Output is correct
4 Correct 0 ms 2180 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2664 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 0 ms 2180 KB Output is correct
4 Correct 0 ms 2180 KB Output is correct
5 Correct 3 ms 2576 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2552 KB Output is correct
2 Correct 3 ms 2576 KB Output is correct
3 Correct 3 ms 2492 KB Output is correct
4 Correct 0 ms 2312 KB Output is correct
5 Correct 0 ms 2312 KB Output is correct
6 Correct 3 ms 2576 KB Output is correct