| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1133622 | Theo830 | 상형문자열 (IOI24_hieroglyphs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "hieroglyphs.h"
vector<int>solve(vector<int>a,vector<int>b){
vector<int>ans;
map<ll,ll>mp1,mp2;
map<ll,vector<ll> >ex,ex2;
ll w = 0;
for(auto x:a){
mp1[x]++;
ex[x].pb(w);
w++;
}
w = 0;
for(auto x:b){
mp2[x]++;
ex2[x].pb(w);
w++;
}
vector<int>A,B;
vector<int>posi,posi2;
ll z = 0;
posi.pb(-1);
posi2.pb(-1);
for(auto x:a){
if(mp1[x] <= mp2[x]){
A.pb(x);
posi.pb(z);
}
z++;
}
z = 0;
ll q = 0;
for(auto x:b){
if(mp2[x] < mp1[x]){
B.pb(x);
}
if(q < A.size() && A[q] == x){
posi2.pb(z);
q++;
}
z++;
}
ll last = a.size();
ll pos = b.size()-1;
bool ok = q == (ll)A.size();
while(!B.empty() && ok){
bool ivra = 0;
ll t;
while(!ex[B.back()].empty() && ex[B.back()].back() >= last){
ex[B.back()].pop_back();
}
if(!ex[B.back()].empty() && ex[B.back()].back() > posi.back()){
ivra = 1;
t = ex[B.back()].back();
}
bool iv = 0;
while(!ex2[B.back()].empty() && ex2[B.back()].back() > pos){
ex2[B.back()].pop_back();
}
if(!ex2[B.back()].empty() && ex2[B.back()].back() > posi2.back()){
iv = 1;
}
ll plast = posi.back();
ll pposi2 = posi2.back();
posi.pop_back();
posi2.pop_back();
ll ppos = pos;
while(ppos >= 0 && A.back() != b[ppos]){
ppos--;
}
ppos--;
bool iv1 = 0,iv2 = 0;
vector<ll>vale;
while(!ex[B.back()].empty() && ex[B.back()].back() >= plast){
vale.pb(ex[B.back()].back());
ex[B.back()].pop_back();
}
if(!ex[B.back()].empty() && ex[B.back()].back() > posi.back()){
iv1 = 1;
}
for(auto x:vale){
ex[B.back()].pb(x);
}
vale.clear();
while(!ex2[B.back()].empty() && ex2[B.back()].back() > ppos){
vale2.pb(ex[B.back()].back());
ex2[B.back()].pop_back();
}
if(!ex2[B.back()].empty() && ex2[B.back()].back() > posi2.back()){
iv2 = 1;
}
for(auto x:vale){
ex2[B.back()].pb(x);
}
if(iv1 && iv2){
ok = 0;
}
posi.pb(plast);
posi2.pb(pposi2);
if(ivra && iv){
last = t;
ans.pb(B.back());
while(pos >= 0 && ans.back() != b[pos]){
pos--;
}
pos--;
B.pop_back();
}
else if(!A.empty()){
last = posi.back();
posi.pop_back();
posi2.pop_back();
ans.pb(A.back());
while(pos >= 0 && ans.back() != b[pos]){
pos--;
}
pos--;
A.pop_back();
}
else{
ok = 0;
}
}
while(!A.empty()){
ans.pb(A.back());
A.pop_back();
}
reverse(all(ans));
pos = 0;
for(auto x:a){
if(pos < ans.size() && ans[pos] == x){
pos++;
}
}
ok &= pos == (ll)ans.size();
pos = 0;
for(auto x:b){
if(pos < ans.size() && ans[pos] == x){
pos++;
}
}
ok &= pos == (ll)ans.size();
if(!ok){
ans.clear();
ans.pb(-1);
}
return ans;
}
vector<int> ucs(std::vector<int> a, std::vector<int> b){
vector<int>a1 = solve(a,b),a2 = solve(b,a);
if(a1 == a2){
return a1;
}
a1.clear();
a1.pb(-1);
return a1;
}
/*
int main() {
int N, M;
assert(2 == scanf("%d%d", &N, &M));
std::vector<int> A(N), B(M);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &A[i]));
for (int j = 0; j < M; j++)
assert(1 == scanf("%d", &B[j]));
fclose(stdin);
std::vector<int> R = ucs(A, B);
int T = (int)R.size();
printf("%d\n", T);
for (int i = 0; i < T; i++)
printf("%s%d", (i == 0 ? "" : " "), R[i]);
printf("\n");
fclose(stdout);
return 0;
}
*/