Submission #147941

#	Time	Username	Problem	Language	Result	Execution time	Memory
147941		lyc	게임판 (CEOI13_board)	C++14	100 / 100	7 ms	1852 KiB

board

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

string parse(string S) {
    vector<int> carry = { 0 };
    vector<int> T = { 1 };
    for (auto& c : S) {
        switch (c) {
            case '1':
                T.push_back(0);
                carry.push_back(0);
                break;
            case '2':
                T.push_back(1);
                carry.push_back(0);
                break;
            case 'L':
                --carry.back();
                break;
            case 'R':
                ++carry.back();
                break;
            case 'U':
                int spill = floor((carry.back() + T.back()) / 2.0);
                T.pop_back();
                carry.pop_back();

                carry.back() += spill;
                break;
        }
    }
    //cout << "T: "; for (int x : T) { cout << x << " "; } cout << endl;
    //cout << "C: "; for (int x : carry) { cout << x << " "; } cout << endl;

    reverse(ALL(T));
    reverse(ALL(carry));
    FOR(i,0,SZ(T)-1) {
        int cur = (T[i] + carry[i] + (1<<20)) % 2;
        int spill = floor((T[i] + carry[i]) / 2.0);
        T[i] = cur;
        if (spill) { if (i == SZ(T)-1) T.push_back(0), carry.push_back(spill); else carry[i+1] += spill; }
    }

    //cout << "T: "; for (int x : T) { cout << x << " "; } cout << endl;
    //cout << "C: "; for (int x : carry) { cout << x << " "; } cout << endl;
    T.pop_back();
    reverse(ALL(T));
    string t = "";
    for (auto& c : T) t += '0'+c;
    return t;
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    string A, B; cin >> A >> B;
    A = parse(A), B = parse(B);

    int ans = 2e5+10;
    if (A > B) swap(A,B);
    //cout << A << " " << B << endl;

    int diff = 0;
    for (int l = 0; diff < ans && l < (int)min(A.length(),B.length()); ++l) {
        diff *= 2;
        diff += B[l]-A[l];
        //cout << diff << " " << (int)A.length()-1-l << " " << (int)B.length()-1-l << endl;
        ans = min(ans, diff + (int)A.length()-1-l + (int)B.length()-1-l);
    }
    cout << ans << endl;
}

• 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