oj.uz

Submission #120220

# Submission time Handle Problem Language Result Execution time Memory
120220 2019-06-24T01:33:07 Z minhtung0404 Board (CEOI13_board) C++17
100 / 100
 72 ms 3960 KB 
#include<bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;

string s, x, tmp;
int n = 100000;

struct node{
    int lazy, Max, Min;
} it[N << 2];

void dolazy(int i, int l, int r){
    if (it[i].lazy == 0) return;
    it[i].lazy = 0;
    swap(it[i].Max, it[i].Min);
    it[i].Max = 3 - it[i].Max;
    it[i].Min = 3 - it[i].Min;
    it[i << 1].lazy ^= 1;
    it[i << 1 | 1].lazy ^= 1;
}

void update(int i, int l, int r, int pos, int val){
    dolazy(i, l, r);
    if (l > pos || pos > r) return;
    if (l == r){
        it[i].Min = it[i].Max = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, pos, val); update(i << 1 | 1, mid+1, r, pos, val);
    it[i].Min = min(it[i << 1].Min, it[i << 1 | 1].Min);
    it[i].Max = max(it[i << 1].Max, it[i << 1 | 1].Max);
}

void rev(int i, int l, int r, int L, int R){
    dolazy(i, l, r);
    if (L > r || l > R) return;
    if (L <= l && r <= R){
        it[i].lazy = true;
        dolazy(i, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    rev(i << 1, l, mid, L, R); rev(i << 1 | 1, mid+1, r, L, R);
    it[i].Min = min(it[i << 1].Min, it[i << 1 | 1].Min);
    it[i].Max = max(it[i << 1].Max, it[i << 1 | 1].Max);
}

int find_1(int i, int l, int r, int pos){
    dolazy(i, l, r);
    if (l > pos || it[i].Min  == 2) return -1;
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int ans = find_1(i << 1 | 1, mid+1, r, pos);
    if (ans == -1) ans = find_1(i << 1, l, mid, pos);
    return ans;
}

int find_2(int i, int l, int r, int pos){
    dolazy(i, l, r);
    if (l > pos || it[i].Max == 1) return -1;
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int ans = find_2(i << 1 | 1, mid+1, r, pos);
    if (ans == -1) ans = find_2(i << 1, l, mid, pos);
    return ans;
}

void get(int i, int l, int r, string& s, int len){
    dolazy(i, l, r);
    if (l > len) return;
    if (l == r){
        s += char('0' + it[i].Min);
        return;
    }
    int mid = (l + r) >> 1;
    get(i << 1, l, mid, s, len); get(i << 1 | 1, mid+1, r, s, len);
}

void solve(string& s){
    int len = 0;
    for (int i = 0; i < (int)s.size(); i++){
        if (s[i] == 'U') len--;
        if (s[i] == '1'){
            len++;
            update(1, 1, n, len, 1);
        }
        if (s[i] == '2'){
            len++;
            update(1, 1, n, len, 2);
        }
        if (s[i] == 'L'){
            int pos = find_2(1, 1, n, len);
            rev(1, 1, n, pos, len);
        }
        if (s[i] == 'R'){
            int pos = find_1(1, 1, n, len);
            rev(1, 1, n, pos, len);
        }
    }
    s = "";
    get(1, 1, n, s, len);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> s >> x;
    solve(s); solve(x);
    int sum = (s.size() + x.size()), dis = 0, Min = sum;
    for (int i = 0; i < min((int)s.size(), (int)x.size()); i++){
        sum -= 2;
        if (abs(dis) > Min) break;
        if (dis == 0){
            dis = s[i] - x[i];
        }
        else{
            dis = dis * 2 + s[i] - x[i];
        }
        Min = min(Min, sum + abs(dis));
    }
    cout << Min;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 768 KB Output is correct
2 Correct 8 ms 512 KB Output is correct
3 Correct 26 ms 768 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 512 KB Output is correct
2 Correct 40 ms 896 KB Output is correct
3 Correct 21 ms 768 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 640 KB Output is correct
2 Correct 37 ms 896 KB Output is correct
3 Correct 22 ms 836 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3832 KB Output is correct
2 Correct 69 ms 3704 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 6 ms 768 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3832 KB Output is correct
2 Correct 71 ms 3860 KB Output is correct
3 Correct 4 ms 636 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 67 ms 3960 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3732 KB Output is correct
2 Correct 70 ms 3704 KB Output is correct
3 Correct 45 ms 3448 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 66 ms 2432 KB Output is correct