Submission #1269545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269545		biank	Hieroglyphs (IOI24_hieroglyphs)	C++20	16 / 100	61 ms	19528 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

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);
}

vi ucs(vi A, vi B) {
    vi cnt_a = buildFreq(A), cnt_b = buildFreq(B);
    vector<vi> where_a = buildWhere(A), where_b = buildWhere(B);
    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 ret;
    while (!w_a.empty() && !w_b.empty()) {
        int x = w_a.back(), y = w_b.back();
        if (common_subsecuence(x, have[x] + 1, y, remainding[y], where_a, where_b)) {
            ret.pb(x), w_a.pop_back(), have[x]++, remainding[x]--;
        } else {
            ret.pb(y), w_b.pop_back(), have[y]++, remainding[y]--;
        }
    }
    while (!w_a.empty()) ret.pb(w_a.back()), w_a.pop_back();
    while (!w_b.empty()) ret.pb(w_b.back()), w_b.pop_back();
    return ret;
}

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