oj.uz

Submission #218925

# Submission time Handle Problem Language Result Execution time Memory
218925 2020-04-03T07:46:46 Z dolphingarlic Board (CEOI13_board) C++14
100 / 100
 99 ms 1020 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const int BASE = 62;

int len_a, len_b;
ll big_a[100000], big_b[100000];

void read(ll *big, int &len) {
    big[0] = 1ll << (BASE - 1);
    len = 1;

    string s;
    cin >> s;
    for (char i : s) {
        switch (i) {
            case '1':
                big[len / BASE] &= ~(1ll << (BASE - 1 - len % BASE));
                len++;
                break;
            case '2':
                big[len / BASE] |= 1ll << (BASE - 1 - len % BASE);
                len++;
                break;
            case 'L':
                big[(len - 1) / BASE] -= 1ll << (BASE - 1 - (len - 1) % BASE);
                for (int j = (len - 1) / BASE; big[j] < 0; j--) {
                    big[j] += 1ll << BASE;
                    big[j - 1]--;
                }
                break;
            case 'R':
                big[(len - 1) / BASE] += 1ll << (BASE - 1 - (len - 1) % BASE);
                for (int j = (len - 1) / BASE; big[j] >= 1ll << BASE; j--) {
                    big[j] -= 1ll << BASE;
                    big[j - 1]++;
                }
                break;
            default:
                len--;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    read(big_a, len_a);
    read(big_b, len_b);

    int ans = INT_MAX, a1 = 0;
    FOR(i, 0, min(len_a, len_b)) {
        a1 = 2 * a1 + (big_a[i / BASE] >> (BASE - 1 - i % BASE) & 1) - (big_b[i / BASE] >> (BASE - 1 - i % BASE) & 1);
        if (abs(a1) > ans) break;
        ans = min(ans, abs(a1) + len_a + len_b - 2 * i - 2);
    }
    cout << ans;
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 6 ms 640 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 796 KB Output is correct
2 Correct 41 ms 768 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 796 KB Output is correct
2 Correct 45 ms 1020 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 95 ms 796 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 768 KB Output is correct
2 Correct 40 ms 892 KB Output is correct
3 Correct 23 ms 768 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 99 ms 808 KB Output is correct