Submission #120220

#	Time	Username	Problem	Language	Result	Execution time	Memory
120220		minhtung0404	Board (CEOI13_board)	C++17	100 / 100	72 ms	3960 KiB

board

#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 / 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