Submission #1269560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269560		biank	Hieroglyphs (IOI24_hieroglyphs)	C++20	44 / 100	50 ms	22416 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define all(x) begin(x), end(x)
#define sz(x) int(x.size())

using vi = vector<int>;
using vb = vector<bool>;

#define pb push_back
#define eb emplace_back

struct FTree {
    int n;
    vi ft;
    FTree(int _n) : n(_n + 9), ft(n, 0) {}
    void update(int pos, int val) {
        for (++pos; pos < n; pos += pos & -pos) ft[pos] += val;
    }
    int get(int pos) {
        int s = 0;
        for (; pos > 0; pos -= pos & -pos) s += ft[pos];
        return s;
    }
    int query(int l, int r) {
        return get(r) - get(l);
    }
};

const int M = 2e5 + 9;

vi buildFreq(vi &a) {
    vi freq(M, 0);
    for (int x : a) freq[x]++;
    return freq;
}

vi subsequence(vi &a, vb &type, bool active) {
    vi w;
    dforn(i, sz(a)) if (type[a[i]] == active) w.pb(a[i]);
    return w;
}

vector<vi> buildWhere(vi &a) {
    vector<vi> where(M);
    forn(i, sz(a)) where[a[i]].pb(i);
    return where;
}

bool check(int x, int c_x, int y, int c_y, const vector<vi> &where) {
    if (c_x == 0) return sz(where[y]) >= c_y;
    if (c_y == 0) return sz(where[x]) >= c_x;
    return sz(where[x]) >= c_x && sz(where[y]) >= c_y && where[x][c_x - 1] < where[y][sz(where[y]) - c_y];
}

bool common_subsecuence(int x, int c_x, int y, int c_y, const vector<vi> &where_a, const vector<vi> &where_b) {
    return check(x, c_x, y, c_y, where_a) && check(x, c_x, y, c_y, where_b);
}

bool is_subseq(vi &s, vi &a) {
    int i = 0, j = 0;
    while (i < sz(s) && j < sz(a)) {
        if (s[i] == a[j]) i++;
        j++;
    }
    return i == sz(s);
}

bool check(vi &A, vi &B, vi &cnt_a, vi &cnt_b, vector<vi> &where_a, vector<vi> &where_b) {
    FTree ft(sz(A));
    forn(i, sz(B)) { // B: x y x, A: y x y
        int x = B[i];
        if (cnt_b[x] == 2 && cnt_a[x] == 1) {
            if (where_b[x][0] == i) ft.update(where_a[x][0], 1);
            else ft.update(where_a[x][0], -1);
        }
        if (cnt_b[x] == 1 && cnt_a[x] == 2 && ft.query(where_a[x][0], where_a[x][1] + 1) > 0) {
            return false;
        }
    }
    return true;
}

vi clear(vi &a, vb &relevant) {
    vi newA;
    for (int x : a) if (relevant[x]) newA.pb(x);
    return newA;
}

void compress(vi &a, vi &id, vi &val, int &m) {
    forn(i, sz(a)) {
        if (id[a[i]] == -1) {
            val.pb(a[i]);
            id[a[i]] = m++;
        }
        a[i] = id[a[i]];
    }
}

vi ucs(vi A, vi B) {
    vi cnt_a = buildFreq(A), cnt_b = buildFreq(B);
    vb relevant(M, false);
    forn(i, M) relevant[i] = min(cnt_a[i], cnt_b[i]) > 0;
    A = clear(A, relevant), B = clear(B, relevant);
    vi id(M, -1), val;
    int m = 0;
    compress(A, id, val, m);
    compress(B, id, val, m);
    cnt_a = buildFreq(A), cnt_b = buildFreq(B);
    vector<vi> where_a = buildWhere(A), where_b = buildWhere(B);
    bool flag = true;
    forn(i, m) flag &= cnt_a[i] + cnt_b[i] <= 3;
    if (flag && !check(A, B, cnt_a, cnt_b, where_a, where_b)) return vi{-1};
    vb type(m);
    forn(i, m) type[i] = cnt_a[i] <= cnt_b[i];
    vi w_a = subsequence(A, type, true), w_b = subsequence(B, type, false);
    vi have(m, 0), remainding(m);
    forn(i, m) remainding[i] = min(cnt_a[i], cnt_b[i]);
    vi c;
    while (!w_a.empty() && !w_b.empty()) {
        int x = w_a.back(), y = w_b.back();
        bool X = common_subsecuence(x, have[x] + 1, y, remainding[y], where_a, where_b);
        bool Y = common_subsecuence(y, have[y] + 1, x, remainding[x], where_a, where_b);
        if (X && Y) return vi{-1};
        if (X) {
            c.pb(x), w_a.pop_back(), have[x]++, remainding[x]--;
        } else {
            c.pb(y), w_b.pop_back(), have[y]++, remainding[y]--;
        }
    }
    while (!w_a.empty()) c.pb(w_a.back()), w_a.pop_back();
    while (!w_b.empty()) c.pb(w_b.back()), w_b.pop_back();
    if (!is_subseq(c, A) || !is_subseq(c, B)) return vi{-1};
    vi ret(sz(c));
    forn(i, sz(c)) ret[i] = val[c[i]];
    return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 16 / 16
• Subtask 5: 0 / 14
• Subtask 6: 0 / 42