oj.uz

Submission #147941

# Submission time Handle Problem Language Result Execution time Memory
147941 2019-08-31T08:52:22 Z lyc Board (CEOI13_board) C++14
100 / 100
 7 ms 1852 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 764 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 760 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 252 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 4 ms 696 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1676 KB Output is correct
2 Correct 6 ms 1660 KB Output is correct
3 Correct 3 ms 656 KB Output is correct
4 Correct 3 ms 504 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1672 KB Output is correct
2 Correct 6 ms 1676 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 7 ms 1724 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1656 KB Output is correct
2 Correct 7 ms 1752 KB Output is correct
3 Correct 6 ms 1484 KB Output is correct
4 Correct 3 ms 608 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 6 ms 1852 KB Output is correct