| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1136753 | Theo830 | Hieroglyphs (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> ucs(std::vector<int> a, std::vector<int> b){
vector<int>ans;
map<ll,ll>mp1,mp2;
map<ll,vector<ll> >ex,ex2;
ll w = 0;
set<ll>E;
for(auto x:a){
E.insert(x);
mp1[x]++;
ex[x].pb(w);
w++;
}
w = 0;
for(auto x:b){
E.insert(x);
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;
}
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();
set<ll>x1,x2,x3;
map<ll,ll>last1,last2,last3;
ll p = 0;
for(auto x:a){
last1[x] = p;
p++;
x1.insert(x);
}
p = 0;
for(auto x:b){
last2[x] = p;
p++;
x2.insert(x);
}
p = 0;
for(auto x:ans){
last3[x] = p;
p++;
x3.insert(ans);
}
if(!ok){
ans.clear();
ans.pb(-1);
}
else{
map<ll,ll>posi1,posi2,posi3;
for(auto x:E){
f(j,0,min(mp1[x],mp2[x])){
while(a[posi1[x]] != x){
if(posi1[x] == last1[x]){
x1.erase(x);
}
posi1[x]++;
}
while(b[posi2[x]] != x){
if(posi2[x] == last2[x]){
x2.erase(x);
}
posi2[x]++;
}
while(ans[posi3[x]] != x){
if(posi3[x] == last3[x]){
x3.erase(x);
}
posi3[x]++;
}
if(posi1[x] == last1[x]){
x1.erase(x);
}
if(posi2[x] == last2[x]){
x2.erase(x);
}
if(posi3[x] == last3[x]){
x3.erase(x);
}
posi1[x]++;
posi2[x]++;
posi3[x]++;
for(auto z:x1){
if(x2.count(z) && !x3.count(z)){
ok = 0;
break;
}
}
}
}
}
if(!ok){
ans.clear();
ans.pb(-1);
}
return ans;
}
/*
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;
}
*/