제출 #1211732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211732		onbert	상형문자열 (IOI24_hieroglyphs)	C++20	3 / 100	42 ms	20556 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<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++) apos[a[i]].push_back(i);
    for (int i=0;i<m;i++) bpos[b[i]].push_back(i);
    vector<int> aans;
    for (int i=0;i<n;i++) if (afreq[a[i]] == 1) aans.push_back(i);
    vector<int> bans;
    for (int i=0;i<m;i++) if (bfreq[b[i]] == 1) bans.push_back(i);

    int asz = aans.size(), bsz = bans.size();
    int apt = 0, bpt = 0;
    vector<int> ans;
    while (apt != asz || bpt != bsz) {
        int take;
        if (apt == asz) take = 1;
        else if (bpt == bsz) take = 0;
        else if (bpos[a[aans[apt]]].size() == 1 && apos[b[bans[bpt]]].size() == 1) {
            if (a[aans[apt]] != b[bans[bpt]]) return {-1};
            take = 2;
        }
        else if (bpos[a[aans[apt]]].size() == 1) take = 1;
        else if (apos[b[bans[bpt]]].size() == 1) take = 0;
        else {
            int aval = a[aans[apt]], bval = b[bans[bpt]];
            int ascore = 0, bscore = 0;
            if (bpos[aval][1] < bans[bpt]) ascore = -1;
            else if (bpos[aval][0] > bans[bpt]) ascore = 1;
            if (apos[bval][1] < aans[apt]) bscore = -1;
            else if (apos[bval][0] > aans[apt]) bscore = 1;
            if (ascore == bscore) return {-1};
            if (ascore < bscore) take = 0;
            else take = 1;
        }
        if (take == 2) {
            ans.push_back(a[aans[apt]]);
            apt++, bpt++;
        } else if (take == 0) {
            int val = a[aans[apt]];
            if (bpt != 0 && bpos[val][0] < bans[bpt]) return {-1};
            ans.push_back(val);
            apt++;
        } else if (take == 1) {
            int val = b[bans[bpt]];
            if (apt != 0 && apos[val][0] < aans[apt]) return {-1};
            ans.push_back(val);
            bpt++;
        }
    }
    return ans;
}

• 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