Submission #1212571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212571		onbert	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	23 ms	15172 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;
bool aiscrit[maxn], biscrit[maxn];
int asz, bsz;
int r[maxn];

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

    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});
        aiscrit[i] = true;
    }
    for (int i=0;i<m;i++) if (bfreq[b[i]] <= afreq[b[i]]) {
        bcrit.push_back({a[i], i});
        biscrit[i] = true;
    }
    asz = acrit.size(), bsz = bcrit.size();

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

    vector<int> ans;
    int apt = -1, bpt = -1;
    for (int i=0;i<bsz;i++) {
        auto [val, pos] = bcrit[i];
        while (apt < r[i] - 1 && bpt < pos) {
            if (apt+1 < n && !aiscrit[apt+1]) apt++;
            else {
                bpt++;
                if (b[bpt] == a[apt+1]) {
                    ans.push_back({b[bpt]});
                    apt++;
                }
            }
        }
        ans.push_back(val);
        bpt = pos;
        while (apt == -1 || a[apt] != val) apt++;
    }
    while (apt+1 < n) {
        apt++;
        if (aiscrit[apt]) ans.push_back(a[apt]);
    }
    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