Submission #1203796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203796		Andrey	Hieroglyphs (IOI24_hieroglyphs)	C++20	18 / 100	52 ms	20200 KiB

hieroglyphs

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

vector<int> pos1[200001];
vector<int> pos2[200001];
vector<int> idk(200001, INT_MAX);

void upd(int a, int c) {
    while(a < idk.size()) {
        idk[a] = min(idk[a],c);
        a+=(a&(-a));
    }
}

int calc(int a) {
    int c = 0,ans = INT_MAX;
    for(int i = 18; i >= 0; i--) {
        if(c+(1 << i) <= a) {
            c+=(1<<i);
            ans = min(ans,idk[c]);
        }
    }
    return ans;
}

int dude(int x, int a) {
    if(pos1[x].size() == 0 || pos1[x][pos1[x].size()-1] < a) {
        return -1;
    }
    int l = 0,r = pos1[x].size()-1;
    while(l < r) {
        int mid = (l+r)/2;
        if(pos1[x][mid] >= a) {
            r = mid;
        }
        else {
            l = mid+1;
        }
    }
    return pos1[x][l];
}

std::vector<int> ucs(std::vector<int> a, std::vector<int> b) {
    vector<int> wow(0);
    vector<int> wut(1,-1);
    for(int i = 0; i < a.size(); i++) {
        pos1[a[i]].push_back(i);
    }
    for(int i = 0; i < b.size(); i++) {
        pos2[b[i]].push_back(i);
    }
    for(int i = 0; i < a.size(); i++) {
        if(pos1[a[i]].size() <= pos2[a[i]].size()) {
            wow.push_back(a[i]);
            wut.push_back(i);
        }
    }
    int y = wow.size()-1;
    vector<int> banana(b.size());
    for(int i = b.size()-1; i >= 0; i--) {
        if(y >= 0 && b[i] == wow[y]) {
            y--;
        }
        banana[i] = y+1;
    }
    vector<int> ans(0);
    y = 1;
    int l = 0;
    for(int i = 0; i < b.size(); i++) {
        if(pos1[b[i]].size() <= pos2[b[i]].size()) {
            continue;
        }
        l = max(l,wut[banana[i]]+1);
        int c = dude(b[i],l);
        if(c == -1) {
            return {-1};
        }
        l = max(l,c+1);
        while(y < wut.size() && wut[y] < c) {
            ans.push_back(wow[y-1]);
            y++;
        }
        ans.push_back(b[i]);
    }
    while(y < wut.size()) {
        ans.push_back(wow[y-1]);
        y++;
    }
    y = 0;
    for(int i = 0; i < a.size(); i++) {
        if(y < ans.size() && ans[y] == a[i]) {
            y++;
        }
    }
    if(y < ans.size()) {
        return {-1};
    }
    y = 0;
    for(int i = 0; i < b.size(); i++) {
        if(y < ans.size() && ans[y] == b[i]) {
            y++;
        }
    }
    if(y < ans.size()) {
        return {-1};
    }
    for(int i = ans.size()-1; i >= 0; i--) {
        int z = ans[i];
        int x = pos1[z][pos1[z].size()-1],y = pos2[z][pos2[z].size()-1];
        if(calc(x) <= y) {
            return {-1};
        }
        x = pos1[z][0]+1;
        y = pos2[z][0]+1;
        upd(x,y);
    }
    return ans;
}

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