Submission #272446

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
272446	2020-08-18T11:50:52 Z	johutha	Board (CEOI13_board)	C++14	100 / 100	122 ms	10360 KB

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.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	0 ms	384 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2940 KB	Output is correct
2	Correct	81 ms	9872 KB	Output is correct
3	Correct	37 ms	9088 KB	Output is correct
4	Correct	1 ms	288 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	1 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	3968 KB	Output is correct
2	Correct	57 ms	9704 KB	Output is correct
3	Correct	35 ms	10104 KB	Output is correct
4	Correct	1 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	107 ms	9848 KB	Output is correct
2	Correct	107 ms	9600 KB	Output is correct
3	Correct	7 ms	1248 KB	Output is correct
4	Correct	8 ms	1388 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	110 ms	9984 KB	Output is correct
2	Correct	122 ms	10284 KB	Output is correct
3	Correct	4 ms	920 KB	Output is correct
4	Correct	6 ms	1024 KB	Output is correct
5	Correct	87 ms	10360 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	111 ms	9548 KB	Output is correct
2	Correct	113 ms	10240 KB	Output is correct
3	Correct	76 ms	9472 KB	Output is correct
4	Correct	11 ms	1664 KB	Output is correct
5	Correct	10 ms	1664 KB	Output is correct
6	Correct	86 ms	10240 KB	Output is correct

Submission #272446

Compilation message