oj.uz

Submission #291257

# Submission time Handle Problem Language Result Execution time Memory
291257 2020-09-05T01:24:51 Z ant101 Board (CEOI13_board) C++14
100 / 100
 112 ms 10292 KB 
#include <iostream>
#include <vector>
#include <cassert>
 
#define int long long
 
using namespace std;
 
struct segtree
{
    vector<pair<int,int>> table;
    vector<int> op;
 
    void apply(int pos, bool v)
    {
        if (v) swap(table[pos].first, table[pos].second);
        op[pos] = op[pos] ^ v;
    }
 
    void propagate(int pos)
    {
        apply(2*pos + 1, op[pos]);
        apply(2*pos + 2, op[pos]);
        op[pos] = 0;
    }
 
    pair<int,int> merge(pair<int,int> p1, pair<int,int> p2)
    {
        return make_pair(max(p1.first, p2.first), max(p1.second, p2.second));
    }
 
    pair<int,int> query(int ql, int qr, int l, int r, int pos)
    {
        if (ql <= l && r <= qr) return table[pos];
        if (r < ql || qr < l) return {-1ll, -1ll};
        propagate(pos);
        return merge(query(ql, qr, l, (l + r) / 2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
    }
 
    void set(int k, int v, int l, int r, int pos)
    {
        if (l == r)
        {
            table[pos] = make_pair((v == 0 ? l : -1ll), (v == 1 ? l : -1ll));
            return;
        }
        propagate(pos);
        if (k <= (l + r)/2) set(k, v, l, (l + r)/2, 2*pos + 1);
        else set(k, v, (l + r)/2 + 1, r, 2*pos + 2);
        table[pos] = merge(table[2*pos + 1], table[2*pos + 2]);
    }
 
    void update(int ql, int qr, int l, int r, int pos)
    {
        if (ql <= l && r <= qr) { apply(pos, 1); return; }
        if (r < ql || qr < l) return;
        propagate(pos);
        update(ql, qr, l, (l + r)/2, 2*pos + 1);
        update(ql, qr, (l + r)/2 + 1, r, 2*pos + 2);
 
        table[pos] = merge(table[2*pos + 1], table[2*pos + 2]);
    }
};
 
vector<bool> process(string ip)
{
    int n = ip.size();
    int cl = 0;
    segtree st;
    st.table.resize(4*n, {-1ll, -1ll});
    st.op.resize(4*n, 0);
 
    for (int i = 0; i < n; i++)
    {
        if (ip[i] == 'U') { st.set(cl - 1, -1, 0, n - 1, 0); cl--; }
        else if (ip[i] == '1') { st.set(cl, 0, 0, n - 1, 0); cl++; }
        else if (ip[i] == '2') { st.set(cl, 1, 0, n - 1, 0); cl++; }
        else if (ip[i] == 'L')
        {
            int lr = st.query(0, n - 1, 0, n - 1, 0).second;
            st.update(lr, cl - 1, 0, n - 1, 0);
        }
        else if (ip[i] == 'R')
        {
            int ll = st.query(0, n - 1, 0, n - 1, 0).first;
            st.update(ll, cl - 1, 0, n - 1, 0);
        }
    }
    vector<bool> res(cl);
    for (int i = 0; i < cl; i++)
    {
        auto p = st.query(i, i, 0, n - 1, 0);
        res[i] = (p.second == i);
    }
    return res;
}
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    string ia, ib;
    cin >> ia >> ib;
 
    vector<bool> a = process(ia);
    vector<bool> b = process(ib);
    int ms = min((int)a.size(), (int)b.size());
 
    for (int i = 0; i < ms; i++)
    {
        if (a[i] == b[i]) continue;
        if (a[i]) { swap(a, b); break; }
        if (b[i]) break;
    }
 
    int dst = 0;
    int res = 1e9;
 
    for (int i = 0; i < ms; i++)
    {
        res = min(res, dst + (int)a.size() + (int)b.size() - 2*i);
        dst *= 2;
        dst += -1ll + (!a[i]) + (b[i]);
        if (dst > (int)1e6) break;
    }
    res = min(res, dst + (int)a.size() + (int)b.size() - 2*ms);
    cout << res << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7476 KB Output is correct
2 Correct 9 ms 2688 KB Output is correct
3 Correct 39 ms 8064 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2940 KB Output is correct
2 Correct 62 ms 9880 KB Output is correct
3 Correct 30 ms 9088 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4096 KB Output is correct
2 Correct 56 ms 9448 KB Output is correct
3 Correct 33 ms 9984 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 9784 KB Output is correct
2 Correct 106 ms 9600 KB Output is correct
3 Correct 7 ms 1248 KB Output is correct
4 Correct 7 ms 1304 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 9984 KB Output is correct
2 Correct 112 ms 10292 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 8 ms 1152 KB Output is correct
5 Correct 85 ms 10240 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 9556 KB Output is correct
2 Correct 110 ms 10292 KB Output is correct
3 Correct 75 ms 9472 KB Output is correct
4 Correct 11 ms 1664 KB Output is correct
5 Correct 11 ms 1664 KB Output is correct
6 Correct 85 ms 10288 KB Output is correct