Submission #272446

#	Time	Username	Problem	Language	Result	Execution time	Memory
272446		johutha	Board (CEOI13_board)	C++14	100 / 100	122 ms	10360 KiB

board

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