Submission #1213887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213887		Sharky	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	30 ms	4376 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define sz(x) (int)x.size()

const int MAX = 200000;

int fa[MAX], fb[MAX], cur[MAX], crit[MAX];

std::vector<int> ucs(std::vector<int> a, std::vector<int> b) {
    int n = sz(a), m = sz(b);
    bool st1 = true;
    if (n == m) {
        vector<int> x = a, y = b;
        sort(all(x)), sort(all(y));
        for (int i = 0; i < n; i++) if (x[i] != i || y[i] != i) st1 = false;
    } else st1 = false;
    if (st1) {
        if (a == b) return a;
        return {-1};
    }
    for (int i = 0; i < n; i++) fa[a[i]]++;
    for (int i = 0; i < m; i++) fb[b[i]]++;
    int sum = 0;
    for (int i = 0; i < MAX; i++) crit[i] = min(fa[i], fb[i]), sum += crit[i];
    int pa = 0, pb = 0;
    vector<int> ucs;
    while (pa < n && pb < m) {
        if (fa[a[pa]] < crit[a[pa]] || fb[b[pb]] < crit[b[pb]]) return {-1};
        if (fa[a[pa]] == crit[a[pa]]) {
            while (pb < m && b[pb] != a[pa]) fb[b[pb]]--, pb++;
            if (pb < m) {
                ucs.push_back(a[pa]);
                crit[a[pa]]--;
                fa[a[pa]]--;
                fb[b[pb]]--;
                pa++, pb++;
            }
        } else if (fb[b[pb]] == crit[b[pb]]) {
            while (pa < n && a[pa] != b[pb]) fa[a[pa]]--, pa++;
            if (pa < n) {
                ucs.push_back(b[pb]);
                crit[b[pb]]--;
                fa[a[pa]]--;
                fb[b[pb]]--;
                pa++, pb++;
            }
        } else if (fa[a[pa]] - 1 >= crit[a[pa]]) {
            fa[a[pa]]--;
            pa++;
        } else if (fb[b[pb]] - 1 >= crit[b[pb]]) {
            fb[b[pb]]--;
            pb++;
        } else return {-1};
    }
    if (sz(ucs) == sum) return ucs;
    return {-1};
}

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