Submission #1214509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214509		Nelt	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	23 ms	8896 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 (ll i = 0; i < n; i++) cnta[a[i]]++;
    for (ll i = 0; i < m; i++) cntb[b[i]]++;
    ll zero = min(cnta[0], cntb[0]), one = min(cnta[1], cntb[1]);
    vector<array<ll,2>> nxtA(n+2), nxtB(m+2);
    nxtA[n][0] = nxtA[n][1] = 1e18;
    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] = 1e18;
    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 = zero, orr = one;
    bool uniq = true;
    vector<int> res;

    for (ll k = 0; k < zero + one; 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