oj.uz

Submission #272431

# Submission time Handle Problem Language Result Execution time Memory
272431 2020-08-18T11:46:04 Z johutha Board (CEOI13_board) C++17
50 / 100
 139 ms 10112 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]);
    }
    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 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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7604 KB Output is correct
2 Correct 12 ms 2688 KB Output is correct
3 Correct 50 ms 8192 KB Output is correct

Subtask #3
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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2940 KB Output is correct
2 Correct 84 ms 9996 KB Output is correct
3 Correct 33 ms 9216 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 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 1 ms 384 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 4096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 10056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 10112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -