Submission #1199228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199228		Octagons	Hieroglyphs (IOI24_hieroglyphs)	C++20	58 / 100	84 ms	27460 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
#define sz(x) int32_t(x.size())
#define all(x) x.begin(),x.end()
const int N = 1e5+5, V = 2e5+5;
vector<int> idsa[V], idsb[V], idd[V], va, vb;
int n, m, cnt[V], frq_habd[V], bit[N];
bool AA[V], BB[V];

void upd(int i, int v) {
    ++i;
    while (i <= m) {
        bit[i] = max(bit[i], v);
        i += (i & -i);
    }
}

int get(int i) {
    ++i;
    int ret = 0;
    while (i) {
        ret = max(ret, bit[i]);
        i -= (i & -i);
    }
    return ret;
}

bool oki(int val, int frq, int val2, int frq2) {
    int i = idsa[val][frq-1];
    int j = idsb[val][frq-1];
    int i2 = idsa[val2][sz(idsa[val2])-frq2];
    int j2 = idsb[val2][sz(idsb[val2])-frq2];
    return (i < i2 && j < j2);
}

std::vector<int> ucs(std::vector<int> A, std::vector<int> B) {
    vector<int> ret;
    n = sz(A), m = sz(B);
    int mx_frq = 0;
    for (int i = 0; i < n; i++) {
        idsa[A[i]].push_back(i);
        frq_habd[A[i]]++;
    }
    for (int i = 0; i < m; i++) {
        idsb[B[i]].push_back(i);
        mx_frq = max(mx_frq, ++frq_habd[B[i]]);
    }
    for (int i = 0; i < V; i++) {
        if (idsa[i].empty() && idsb[i].empty())continue;
        if (sz(idsa[i]) <= sz(idsb[i])) {
            AA[i] = true;
        } else {
            BB[i] = true;
        }
    }
    for (int i = 0; i < n; i++) {
        if (AA[A[i]]) {
            va.push_back(i);
        }
    }
    for (int i = 0; i < m; i++) {
        if (BB[B[i]]) {
            vb.push_back(i);
        }
    }
    int i = 0, j = 0;
    while (i < sz(va) || j < sz(vb)) {
        if (j == sz(vb)) {
            ret.push_back(A[va[i++]]);
            cnt[ret.back()]++;
            continue;
        }
        if (i == sz(va)) {
            ret.push_back(B[vb[j++]]);
            continue;
        }
        bool fri = false, frj = false;
        int val1 = A[va[i]], val2 = B[vb[j]];
        if (oki(val1, 1 + cnt[val1], val2, sz(idsb[val2]) - cnt[val2])) {
            fri = true;
        }
        if (oki(val2, 1 + cnt[val2], val1, sz(idsa[val1]) - cnt[val1])) {
            frj = true;
        }
        if (fri && frj) {
            ret.clear();
            ret.push_back(-1);
            return ret;
        } else if (fri) {
            ret.push_back(A[va[i++]]);
            cnt[ret.back()]++;
        } else {
            ret.push_back(B[vb[j++]]);
            cnt[ret.back()]++;
        }
    }
    j = 0;
    for (int i = 0; i < n && j < sz(ret); i++) {
        if (A[i] == ret[j]) {
            j++;
        }
    }
    if (j < sz(ret)) {
        ret.clear();
        ret.push_back(-1);
        return ret;
    }
    j = 0;
    for (int i = 0; i < m && j < sz(ret); i++) {
        if (B[i] == ret[j]) {
            j++;
        }
    }
    if (j < sz(ret)) {
        ret.clear();
        ret.push_back(-1);
        return ret;
    }
    if (max(n, m) <= 3000 || mx_frq <= 5) {
        for (int i = 0; i < sz(ret); i++) {
            idd[ret[i]].push_back(i);
        }
        for (int i = 0; i < V; i++) {
            reverse(all(idsb[i]));
        }
        for (int i = 0; i < n; i++) {
            for (auto &j : idsb[A[i]]) {
                int habd = get(j - 1);
                int bruh = lower_bound(all(idd[A[i]]), habd) - idd[A[i]].begin();
                if (bruh == sz(idd[A[i]])) {
                    ret.clear();
                    ret.push_back(-1);
                    return ret;
                }
                upd(j, idd[A[i]][bruh] + 1);
            }
        }
    }
    return ret;
}

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