Submission #1214512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214512		Nelt	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	22 ms	8520 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

std::vector<int> ucs(std::vector<int> a, std::vector<int> b)
{
    if (a.size() > b.size())
        swap(a, b);
    ll n = a.size(), m = b.size();
    ll cnta[2] = {0, 0}, cntb[2] = {0, 0};
    for (int x : a)
        cnta[x]++;
    for (int x : b)
        cntb[x]++;
    ll z = min(cnta[0], cntb[0]);
    ll o = min(cnta[1], cntb[1]);

    const ll INF = 1e18;
    vector<array<ll, 2>> nxtA(n + 2), nxtB(m + 2);
    nxtA[n][0] = nxtA[n][1] = INF;
    for (ll i = n - 1; i >= 0; i--)
    {
        nxtA[i] = nxtA[i + 1];
        nxtA[i][a[i]] = i + 1;
    }
    nxtB[m][0] = nxtB[m][1] = INF;
    for (ll i = m - 1; i >= 0; i--)
    {
        nxtB[i] = nxtB[i + 1];
        nxtB[i][b[i]] = i + 1;
    }

    vector<ll> suf0A(n + 2), suf1A(n + 2), suf0B(m + 2), suf1B(m + 2);
    for (ll i = n - 1; i >= 0; i--)
    {
        suf0A[i] = suf0A[i + 1] + (a[i] == 0);
        suf1A[i] = suf1A[i + 1] + (a[i] == 1);
    }
    for (ll i = m - 1; i >= 0; i--)
    {
        suf0B[i] = suf0B[i + 1] + (b[i] == 0);
        suf1B[i] = suf1B[i + 1] + (b[i] == 1);
    }

    ll pa = 0, pb = 0;
    ll zr = z, orr = o;
    bool uniq = true;
    vector<int> res;
    res.reserve(z + o);

    for (ll k = 0; k < z + o; k++)
    {
        ll na0 = nxtA[pa][0], nb0 = nxtB[pb][0];
        bool can0 = zr > 0 && na0 <= n && nb0 <= m && suf1A[na0] >= orr && suf1B[nb0] >= orr;
        ll na1 = nxtA[pa][1], nb1 = nxtB[pb][1];
        bool can1 = orr > 0 && na1 <= n && nb1 <= m && suf0A[na1] >= zr && suf0B[nb1] >= zr;

        if (can0 && can1)
            return {-1};
        if (can0)
        {
            res.push_back(0);
            pa = na0;
            pb = nb0;
            zr--;
        }
        else if (can1)
        {
            res.push_back(1);
            pa = na1;
            pb = nb1;
            orr--;
        }
        else
            return {-1};
    }
    return res;
}

• 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