Submission #1213212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213212		onbert	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	1096 ms	25540 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, maxval = 2e5 + 5;
int n, m;
vector<int> a, b;
int afreq[maxval], bfreq[maxval];
vector<int> apos[maxval], bpos[maxval];
vector<pair<int,int>> acrit, bcrit;
int asz, bsz;
int l[maxn], r[maxn];
vector<int> vec[maxn];

int aqry(int val, int l, int r) {
    if (l > r) return 0;
    return upper_bound(apos[val].begin(), apos[val].end(), r) - lower_bound(apos[val].begin(), apos[val].end(), l);
}

int bqry(int val, int l, int r) {
    if (l > r) return 0;
    return upper_bound(bpos[val].begin(), bpos[val].end(), r) - lower_bound(bpos[val].begin(), bpos[val].end(), l);
}

int af[maxval], bf[maxval];
bool ok(int id) {
    for (int i=0;i<maxval;i++) af[i] = bf[i] = 0;
    int apt = l[id], bpt = bcrit[id].second;
    int cnt = 0, siz = 0;
    for (int i=id+1;i<bsz;i++) {
        siz += vec[i-1].size();
        while (apt < r[i]) {
            apt++;
            int val = a[apt];
            if (afreq[val] < bfreq[val]) {
                cnt -= min(af[val], bf[val]);
                af[val]++;
                cnt += min(af[val], bf[val]);
            }
        }
        while (bpt < bcrit[i].second) {
            bpt++;
            int val = b[bpt];
            if (afreq[val] < bfreq[val]) {
                cnt -= min(af[val], bf[val]);
                bf[val]++;
                cnt += min(af[val], bf[val]);
            }
        }
        if (cnt != siz) return 0;
    }
    return 1;
}

vector<int> ucs(vector<int> A, vector<int> B) {
    for (int i:A) afreq[i]++;
    for (int i:B) bfreq[i]++;
    a.push_back(2e5 + 1), b.push_back(2e5 + 1);
    for (int i:A) if (bfreq[i]) a.push_back(i);
    for (int i:B) if (afreq[i]) b.push_back(i);
    a.push_back(2e5 + 2), b.push_back(2e5 + 2);

    n = a.size(), m = b.size();
    for (int i=0;i<n;i++) if (afreq[a[i]] < bfreq[a[i]]) {
        acrit.push_back({a[i], i});
    }
    for (int i=0;i<m;i++) if (bfreq[b[i]] <= afreq[b[i]]) {
        bcrit.push_back({b[i], i});
    }
    asz = acrit.size(), bsz = bcrit.size();

    for (int i=0;i<n;i++) apos[a[i]].push_back(i);
    for (int i=0;i<m;i++) bpos[b[i]].push_back(i);

    int pt = bsz;
    for (int i=n-1;i>=0;i--)  if (pt-1 >= 0 && bcrit[pt-1].first == a[i]) pt--, r[pt] = i;
    pt = -1;
    for (int i=0;i<n;i++) if (pt+1 < bsz && bcrit[pt+1].first == a[i]) pt++, l[pt] = i;
    if (pt != bsz-1) return {-1};

    vector<int> ans;
    int apt = -1, bpt = -1, nxt = -1;
    for (int i=0;i<bsz;i++) {
        auto [val, pos] = bcrit[i];
        // cout << "i " << i << endl;
        while (apt+1 < asz && acrit[apt+1].second < r[i] && bpt < pos) {
            bpt++;
            if (b[bpt] == acrit[apt+1].first) {
                vec[i-1].push_back({b[bpt]});
                ans.push_back(b[bpt]);
                apt++;
                // cout << acrit[apt].second << endl;
            }
        }
        if (i != 0 && i != bsz-1) ans.push_back(val);
        nxt = *upper_bound(apos[val].begin(), apos[val].end(), nxt);
        if (apt != -1) nxt = max(*upper_bound(apos[val].begin(), apos[val].end(), acrit[apt].second), nxt);
            // cout << "thing " << i-1 << " " << val << " " << apt << endl;
            // cout << acrit[apt].second << " " <<  acrit[apt+1].second << " " << nxt << endl;
        if (apt+1 < asz && acrit[apt+1].second < nxt) return {-1};
        bpt = pos;
    }
    if (ans.size() + 2 != asz + bsz) return {-1};
    // for (int i=0;i<bsz-1;i++) if (!ok(i)) return {-1};
    for (int i=0;i<bsz-1;i++) if (!ok(i)) return {-1};
    // for (int i=0;i<bsz-1;i++) if (!ok(i, i+1)) return {-1};
    return ans;
}

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