oj.uz

Submission #1099850

# Submission time Handle Problem Language Result Execution time Memory
1099850 2024-10-12T05:36:36 Z model_code Hieroglyphs (IOI24_hieroglyphs) C++17
58 / 100
 537 ms 84712 KB 
// incorrect/felix-multiple-heuristics-efficient.cpp

#include "hieroglyphs.h"
#include<bits/stdc++.h>


using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ii = pair<int, int>;

namespace tomek {
    

constexpr int alphabet = 200'001;

vector<int> _ucs(
    const vector<int> text_a,
    const vector<int> text_b)
{
  const int na = text_a.size();
  const int nb = text_b.size();

  vector<vector<int>> positions_a(alphabet);
  vector<vector<int>> positions_b(alphabet);

  for (int i=0; i<na; ++i) {
    positions_a[text_a[i]].push_back(i);
  }
  for (int i=0; i<nb; ++i) {
    positions_b[text_b[i]].push_back(i);
  }

  vector<int> next_a(alphabet, 0);
  vector<int> next_b(alphabet, 0);
  int pos_a = 0;
  int pos_b = 0;
  vector<int> result;

  while (pos_a < na && pos_b < nb) {
    int ta = text_a[pos_a];
    int tb = text_b[pos_b];
    if (ta == tb) {
      result.push_back(ta);
      ++pos_a;
      ++pos_b;
      continue;
    }

    for (int t : {ta, tb}) {
      while (next_a[t] < int(positions_a[t].size()) && positions_a[t][next_a[t]] < pos_a) {
        ++next_a[t];
      }
      while (next_b[t] < int(positions_b[t].size()) && positions_b[t][next_b[t]] < pos_b) {
        ++next_b[t];
      }
    }

    int left_ta_self = int(positions_a[ta].size()) - next_a[ta];
    int left_ta_opp = int(positions_b[ta].size()) - next_b[ta];
    int left_tb_self = int(positions_b[tb].size()) - next_b[tb];
    int left_tb_opp = int(positions_a[tb].size()) - next_a[tb];

    if (left_ta_opp == 0) {
      ++pos_a;
      continue;
    }
    if (left_tb_opp == 0) {
      ++pos_b;
      continue;
    }
    if (left_ta_self <= left_ta_opp) {
      if (left_tb_self <= left_tb_opp) {
        return {-1};
      } else {
        ++pos_b;
        continue;
      }
    } else {
      if (left_tb_self <= left_tb_opp) {
        ++pos_a;
        continue;
      } else {
        int pos_ta_opp = positions_b[ta][next_b[ta]];
        int pos_tb_opp = positions_a[tb][next_a[tb]];
        int last_ta = positions_a[ta][next_a[ta] + left_ta_self - left_ta_opp];
        int last_tb = positions_b[tb][next_b[tb] + left_tb_self - left_tb_opp];
        if (last_ta < pos_tb_opp) {
          if (last_tb < pos_ta_opp) {
            return {-1};
          } else {
            ++pos_b;
            continue;
          }
        } else {
          if (last_tb < pos_ta_opp) {
            ++pos_a;
            continue;
          } else {
            return {-1};
          }
        }
      }
    }
  }

  return result;
}


    vector<int> ucs(vector<int> a, vector<int> b) {
    vector<int> r1 = _ucs(a, b);
    std::reverse(a.begin(), a.end());
    std::reverse(b.begin(), b.end());
    vector<int> r2 = _ucs(a, b);
    std::reverse(r2.begin(), r2.end());
    return (r1 == r2) ? r1 : vector<int>({-1});
    }
}

namespace yiping_solexist {
typedef pair<int,int> pii;

struct Data
{
	int d;
	vector<int> a, cnt, rnk;
	vector< vector<int> > pos;
	
	Data(vector<int> _a, int _d)
	{
		a = _a; d = _d;
		cnt.resize(d); pos.resize(d); rnk.resize(a.size());
		for(int i=0; i<(int)a.size(); ++i)
		{
			int x = a[i];
			rnk[i] = cnt[x]; ++cnt[x];
			pos[x].emplace_back(i);
		}
	}
	bool check(int x,int cx,int y,int cy) const
	{
		if(cx > (int)pos[x].size() || cy > (int)pos[y].size())
			return 0;
		if(cx == 0 || cy == 0) return 1;
		return pos[x][cx - 1] < pos[y][(int)pos[y].size() - cy];
	}
};

vector<int> get_cand(const Data &aa, const Data &bb)
{
	int d = aa.d;
	vector<int> type(d), need(d);
	for(int i=0; i<d; ++i)
	{
		type[i] = aa.cnt[i] <= bb.cnt[i]? 0: 1;
		need[i] = min(aa.cnt[i], bb.cnt[i]);
	}
	
	vector<pii> veca, vecb;
	for(int i=0; i<(int)aa.a.size(); ++i)
		if(type[aa.a[i]] == 0)
			veca.emplace_back(aa.a[i], aa.rnk[i]);
	for(int i=0; i<(int)bb.a.size(); ++i)
		if(type[bb.a[i]] == 1)
			vecb.emplace_back(bb.a[i], bb.rnk[i]);
	
	auto check = [&] (pii x,pii y)
	{
		return aa.check(x.first, x.second + 1, y.first, need[y.first] - y.second)
		    && bb.check(x.first, x.second + 1, y.first, need[y.first] - y.second);
	};
	
	vector<int> c;
	int i = 0, j = 0;
	while(i<(int)veca.size() && j<(int)vecb.size())
	{
		bool tx = check(veca[i], vecb[j]);
		bool ty = check(vecb[j], veca[i]);
		
		if(tx == ty) return {-1};
		
		if(tx) c.emplace_back(veca[i].first), ++i;
		else c.emplace_back(vecb[j].first), ++j;
	}
	
	while(i<(int)veca.size()) c.emplace_back(veca[i].first), ++i;
	while(j<(int)vecb.size()) c.emplace_back(vecb[j].first), ++j;
	
	return c;
}

bool is_invalid(const vector<int> &c)
{
	return c.size() == 1 && c[0] == -1;
}

vector<int> ucs(vector<int> a, vector<int> b)
{
	int d = 0;
	for(auto t: a)
		d = max(d, t + 1);
	for(auto t: b)
		d = max(d, t + 1);
	
	Data aa(a, d), bb(b, d);
	
	auto c = get_cand(aa, bb);
	if(is_invalid(c)) return c;
	
	return c;
}
}

namespace yiping_wa {
    #include<bits/stdc++.h>
#include"hieroglyphs.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

struct Data
{
	int d;
	vector<int> a, cnt, rnk;
	vector< vector<int> > pos;
	
	Data(vector<int> _a, int _d)
	{
		a = _a; d = _d;
		cnt.resize(d); pos.resize(d); rnk.resize(a.size());
		for(int i=0; i<(int)a.size(); ++i)
		{
			int x = a[i];
			rnk[i] = cnt[x]; ++cnt[x];
			pos[x].emplace_back(i);
		}
	}
	bool check(int x,int cx,int y,int cy) const
	{
		if(cx > (int)pos[x].size() || cy > (int)pos[y].size())
			return 0;
		if(cx == 0 || cy == 0) return 1;
		return pos[x][cx - 1] < pos[y][(int)pos[y].size() - cy];
	}
	int get_next(int i,int x) const
	{
		auto it = lower_bound(pos[x].begin(), pos[x].end(), i);
		return it == pos[x].end()? (int)a.size(): *it;
	}
};

vector<int> get_cand(const Data &aa, const Data &bb)
{
	int d = aa.d;
	vector<int> type(d), need(d);
	for(int i=0; i<d; ++i)
	{
		type[i] = aa.cnt[i] <= bb.cnt[i]? 0: 1;
		need[i] = min(aa.cnt[i], bb.cnt[i]);
	}
	
	vector<pii> veca, vecb;
	for(int i=0; i<(int)aa.a.size(); ++i)
		if(type[aa.a[i]] == 0)
			veca.emplace_back(aa.a[i], aa.rnk[i]);
	for(int i=0; i<(int)bb.a.size(); ++i)
		if(type[bb.a[i]] == 1)
			vecb.emplace_back(bb.a[i], bb.rnk[i]);
	
	auto check = [&] (pii x,pii y)
	{
		return aa.check(x.first, x.second + 1, y.first, need[y.first] - y.second)
		    && bb.check(x.first, x.second + 1, y.first, need[y.first] - y.second);
	};
	
	vector<int> c;
	int i = 0, j = 0;
	while(i<(int)veca.size() && j<(int)vecb.size())
	{
		bool tx = check(veca[i], vecb[j]);
		bool ty = check(vecb[j], veca[i]);
		
		if(tx == ty) return {-1};
		
		if(tx) c.emplace_back(veca[i].first), ++i;
		else c.emplace_back(vecb[j].first), ++j;
	}
	
	while(i<(int)veca.size()) c.emplace_back(veca[i].first), ++i;
	while(j<(int)vecb.size()) c.emplace_back(vecb[j].first), ++j;
	
	return c;
}

bool is_invalid(const vector<int> &c)
{
	return c.size() == 1 && c[0] == -1;
}

bool is_subseq(const vector<int> &a, const vector<int> &c)
{
	int j = 0;
	for(int i=0; i<(int)a.size() && j<(int)c.size(); ++i)
		if(a[i] == c[j]) ++j;
	return j >= (int)c.size();
}

vector<int> ucs(vector<int> a, vector<int> b)
{
	int d = 0;
	for(auto t: a)
		d = max(d, t + 1);
	for(auto t: b)
		d = max(d, t + 1);
	
	Data aa(a, d), bb(b, d);
	
	auto c = get_cand(aa, bb);
	if(is_invalid(c)) return c;
	
	if(!is_subseq(a, c)) return {-1};
	if(!is_subseq(b, c)) return {-1};
	
	Data cc(c, d);
	
	const int LIM = 3000;
	const int pa = min(LIM, (int)a.size());
	const int pb = min(LIM, (int)b.size());
	
	int len_a = 0, len_b = 0;
	for(int i=(int)a.size()-1; i>=pa; --i)
		if(len_a < (int)c.size() && a[i] == c[(int)c.size() - len_a - 1])
			++len_a;
	for(int i=(int)b.size()-1; i>=pb; --i)
		if(len_b < (int)c.size() && b[i] == c[(int)c.size() - len_b - 1])
			++len_b;
	
	vector< vector<int> > dp(pa+1, vector<int>(pb+1));
	
	for(int i=0; i<=pa; ++i)
		for(int j=0; j<=pb; ++j)
		{
			if(i) dp[i][j] = max(dp[i][j], dp[i-1][j]);
			if(j) dp[i][j] = max(dp[i][j], dp[i][j-1]);
			if(i && j && a[i-1] == b[j-1])
			{
				dp[i][j] = max(dp[i][j], cc.get_next(dp[i-1][j-1], a[i-1]) + 1);
				if(dp[i][j] + min(len_a, len_b) > (int)c.size())
					return {-1};
			}
		}
	return c;
}
}

namespace felix_wa_jumps {
    

int ALPHABET_SIZE = 0;

bool is_subsequence(const vi& a, const vi& b) {
    int j = 0;
    for (int x : a) {
        if (j < (int)b.size() && b[j] == x) {
            j++;
        }
    }
    return j == (int)b.size();
}

vi get_candidate(const vi& a, const vi& b) {
    int n = a.size();
    int m = b.size();

    vi occ_a(ALPHABET_SIZE, 0);
    vi occ_b(ALPHABET_SIZE, 0);
    for (int i=0; i < n; ++i) {
        occ_a[a[i]]++;
    }
    for (int i=0; i < m; ++i) {
        occ_b[b[i]]++;
    }

    vi c;
    queue<int> qa;
    queue<int> qb;

    for (int i=0; i < n; ++i) {
        if (occ_a[a[i]] <= occ_b[a[i]]) {
            qa.push(i);
        }
    }
    for (int i=0; i < m; ++i) {
        if (occ_a[b[i]] > occ_b[b[i]]) {
            qb.push(i);
        }
    }

    int i_a_curr = 0;
    int i_b_curr = 0;
    int i_a_next = 0;
    int i_b_next = 0;
    vi occ_a_curr = vi(occ_a);
    vi occ_a_next = vi(occ_a);
    vi occ_b_curr = vi(occ_b);
    vi occ_b_next = vi(occ_b);

    while(!qa.empty() && !qb.empty()) {
        while(i_a_next < qa.front()) {
            occ_a_next[a[i_a_next]]--;
            i_a_next++;
        }
        while(i_b_next < qb.front()) {
            occ_b_next[b[i_b_next]]--;
            i_b_next++;
        }

        int x = a[i_a_next];
        int y = b[i_b_next];

        int occ_x = occ_a_next[x];
        int occ_y = occ_b_next[y];

        bool a_good = (occ_a_next[y] >= occ_y && occ_b_curr[x] > occ_b_next[x]);
        bool b_good = (occ_b_next[x] >= occ_x && occ_a_curr[y] > occ_a_next[y]);

        if (a_good && b_good) return {-1};
        if (!a_good && !b_good) return {-1};

        if(a_good) {
            c.push_back(x);
            qa.pop();
            while(i_a_curr <= i_a_next) {
                occ_a_curr[a[i_a_curr]]--;
                i_a_curr++;
            }
            while(b[i_b_curr] != x) {
                occ_b_curr[b[i_b_curr]]--;
                i_b_curr++;
            }
            occ_b_curr[b[i_b_curr]]--;
            i_b_curr++;
        }
        else {
            c.push_back(y);
            qb.pop();
            while(i_b_curr <= i_b_next) {
                occ_b_curr[b[i_b_curr]]--;
                i_b_curr++;
            }
            while(a[i_a_curr] != y) {
                occ_a_curr[a[i_a_curr]]--;
                i_a_curr++;
            }
            occ_a_curr[a[i_a_curr]]--;
            i_a_curr++;
        }
    }

    while(!qa.empty()) {
        c.push_back(a[qa.front()]);
        qa.pop();
    }
    while(!qb.empty()) {
        c.push_back(b[qb.front()]);
        qb.pop();
    }

    return ((is_subsequence(a, c) && is_subsequence(b, c)) ? c : vi({-1}));
}



bool verify_jump(const vi& a, const vi& b, const vi& c) {
    if (c == vi({-1})) return false;
    if (c == vi()) return true; 
    int n = a.size();
    int m = b.size();
    int l = c.size();

    vi occ_a(ALPHABET_SIZE, 0);
    vi occ_b(ALPHABET_SIZE, 0);
    vi occ_c(ALPHABET_SIZE, 0);
    vvi pos_a(ALPHABET_SIZE);
    vvi pos_b(ALPHABET_SIZE);
    vvi pos_c(ALPHABET_SIZE);
    for (int i=0; i < n; ++i) {
        occ_a[a[i]]++;
        pos_a[a[i]].push_back(i);
    }
    for (int i=0; i < m; ++i) {
        occ_b[b[i]]++;
        pos_b[b[i]].push_back(i);
    }
    for (int i=0; i < l; ++i) {
        occ_c[c[i]]++;
        pos_c[c[i]].push_back(i);
    }

    vi pos_c_idx(ALPHABET_SIZE);
    vi jump_left(l);
    for (int i=0; i < l; ++i) jump_left[i] = i;
    int c_idx = 0;

    for (int j=0; j < m; ++j) {
        int idx = pos_c_idx[b[j]];
        if (idx < occ_c[b[j]]) {
            jump_left[pos_c[b[j]][idx]] = min(jump_left[pos_c[b[j]][idx]], c_idx);
            pos_c_idx[b[j]]++;
        }
        if (b[j] == c[c_idx]) {
           // pos_c_idx[b[j]]++;
            c_idx++;
            if (c_idx == l) break;
        }
        
    }

    vi jump_right(l);
    for (int i=0; i < l; ++i) jump_right[i] = i;
    c_idx--;
    
    for (int i=n-1; i > -1; --i) {
         int idx = pos_c_idx[a[i]]-1;
        if (idx > -1) {
            jump_right[pos_c[a[i]][idx]] = max(jump_right[pos_c[a[i]][idx]], c_idx);
            pos_c_idx[a[i]]--;
        }
        if (a[i] == c[c_idx]) {
            //pos_c_idx[a[i]]--;
            c_idx--;
            if (c_idx < 0) break;
        }
        
    }

    vector<ii> stack_jump;


    for (int k=0; k < l; ++k) {
        while (!stack_jump.empty() && stack_jump.back().second < k) {
            stack_jump.pop_back();
        }
        if (!stack_jump.empty() && stack_jump.back().first >= jump_left[k]) {
            return false;
        }
        while (!stack_jump.empty() && stack_jump.back().second < jump_right[k]) {
            stack_jump.pop_back();
        }
        stack_jump.emplace_back(k, jump_right[k]);
        
    }

    
   

   
    return true;
}

bool verify(const vi& a, const vi& b, const vi& c) {
    return verify_jump(a, b, c) && verify_jump(b, a, c);
}

vector<int> ucs(vector<int> a, vector<int> b) {
    for (int x : a) ALPHABET_SIZE = max(ALPHABET_SIZE, x+1);
    for (int x : b) ALPHABET_SIZE = max(ALPHABET_SIZE, x+1);

    vi c = get_candidate(a, b);
    if (verify(a, b, c)) return c;
    return {-1};
}

}

namespace radewoosh {

    //Mateusz Radecki, O(n+m)
#include "hieroglyphs.h"

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

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=1007*1000;

int n, m;

int ilea[nax];
int ileb[nax];

int potrzebuje[nax];

vi pozy[nax];

int potrzebujewa[nax];
int potrzebujewb[nax];

vi licz_harde(vi a, vi b)
{
	n=a.size();
	m=b.size();
	for (int i=0; i<nax; i++)
		ilea[i]=ileb[i]=0;
	for (int i : a)
		ilea[i]++;
	for (int i : b)
		ileb[i]++;
	vector<pii> za, zb;
	for (int i=0; i<n; i++)
		if (ilea[a[i]]<=ileb[a[i]])
			za.push_back({a[i], i});
	for (int i=0; i<m; i++)
		if (ilea[b[i]]>ileb[b[i]])
			zb.push_back({b[i], i});
	
	{
		potrzebujewa[zb.size()]=n;
		int wsk=zb.size();
		for (int i=n-1; i>=0; i--)
		{
			if (wsk && zb[wsk-1].first==a[i])
			{
				wsk--;
				potrzebujewa[wsk]=i;
			}
		}
	}
	{
		potrzebujewb[za.size()]=m;
		int wsk=za.size();
		for (int i=m-1; i>=0; i--)
		{
			if (wsk && za[wsk-1].first==b[i])
			{
				wsk--;
				potrzebujewb[wsk]=i;
			}
		}
	}
	
	vi ret;
	int wska=0;
	int wskb=0;
	int gdz=0;
	for (int i : a)
	{
		if (wska<(int)za.size() && i==za[wska].first)
		{
			while(gdz<m && b[gdz]!=i)
				gdz++;
			if (gdz==m)
				return {-1};
			gdz++;
			ret.push_back(i);
			wska++;
		}
		if (wskb<(int)zb.size() && i==zb[wskb].first && gdz<=zb[wskb].second && potrzebujewb[wska]>zb[wskb].second)
		{
			ret.push_back(i);
			gdz=zb[wskb].second+1;
			wskb++;
		}
	}
	
	if ((int)ret.size()<(int)za.size()+(int)zb.size())
		return {-1};
	
	return ret;
}

vi licz_proste(vi a, vi b, int numwy)
{
	n=a.size();
	m=b.size();
	for (int i=0; i<nax; i++)
		ilea[i]=ileb[i]=0;
	for (int i : a)
		ilea[i]++;
	for (int i : b)
		ileb[i]++;
	vector<pii> za;
	for (int i=0; i<n; i++)
		if (ilea[a[i]]<=ileb[a[i]]-numwy)
			za.push_back({a[i], i});
	
	{
		potrzebuje[za.size()]=m;
		int wsk=za.size();
		for (int i=m-1; i>=0; i--)
		{
			if (wsk && za[wsk-1].first==b[i])
			{
				wsk--;
				potrzebuje[wsk]=i;
			}
		}
		if (wsk)
			return {-1};
	}
	
	for (int i=0; i<nax; i++)
		pozy[i].clear();
	for (int i=m-1; i>=0; i--)
		pozy[b[i]].push_back(i);
	
	vi ret;
	int wsk=0;
	int gdz=0;
	for (int i : a)
	{
		if (wsk<(int)za.size() && i==za[wsk].first)
		{
			while(gdz<m && b[gdz]!=i)
				gdz++;
			assert(gdz<m);
			gdz++;
			ret.push_back(i);
			wsk++;
		}
		else
		{
			while(!pozy[i].empty() && pozy[i].back()<gdz)
				pozy[i].pop_back();
			if (!pozy[i].empty() && potrzebuje[wsk]>pozy[i].back())
			{
				ret.push_back(i);
				gdz=pozy[i].back()+1;
			}
		}
	}
	
	return ret;
}

vi prosty(vi a, vi b)
{
	n=a.size();
	m=b.size();
	for (int i=0; i<nax; i++)
		pozy[i].clear();
	for (int i=m-1; i>=0; i--)
		pozy[b[i]].push_back(i);
	int gdz=0;
	vi ret;
	for (int i : a)
	{
		while(!pozy[i].empty() && pozy[i].back()<gdz)
			pozy[i].pop_back();
		if (!pozy[i].empty())
		{
			ret.push_back(i);
			gdz=pozy[i].back()+1;
		}
	}
	return ret;
}

int zawiera(vi kto, vi kogo)
{
	int wsk=0;
	for (int i : kto)
		if (wsk<(int)kogo.size() && i==kogo[wsk])
			wsk++;
	return wsk==(int)kogo.size();
}

vi _ucs(vi a, vi b)
{
	vi odp=licz_harde(a, b);
	vi raz=licz_proste(a, b, 0);
	vi dwa=licz_proste(b, a, 1);
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	vi trz=licz_proste(a, b, 0);
	vi czt=licz_proste(b, a, 1);
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	reverse(trz.begin(), trz.end());
	reverse(czt.begin(), czt.end());
	
	vi x=prosty(a, b);
	vi y=prosty(b, a);
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	vi z=prosty(a, b);
	vi w=prosty(b, a);
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	reverse(z.begin(), z.end());
	reverse(w.begin(), w.end());
	
	if (zawiera(odp, raz) && zawiera(odp, dwa) && zawiera(odp, trz) && zawiera(odp, czt) && zawiera(odp, x) && zawiera(odp, y) && zawiera(odp, z) && zawiera(odp, w))
		return odp;
	return {-1};
}

vi ucs(vi a, vi b) {
	//return _ucs(a, b);

    vi cpref;
    vi csuf;
    
    while (!a.empty() && !b.empty() && a.back() == b.back()) {
        csuf.push_back(a.back());
        a.pop_back();
        b.pop_back();
    }

    reverse(csuf.begin(), csuf.end());

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    while (!a.empty() && !b.empty() && a.back() == b.back()) {
        cpref.push_back(a.back());
        a.pop_back();
        b.pop_back();
    }


    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    vi rc = _ucs(a, b);
    if (rc == vi({-1})) return rc;

    vi c;
    for (int x : cpref) c.push_back(x);
    for (int x : rc) c.push_back(x);
    for (int x : csuf) c.push_back(x);
    return c;
}

}

//erases non-common elements
void clean(vi& a, vi& b) {
    vi ap;
    vi bp;
    set<int> as;
    set<int> bs;
    for (int x : a) as.insert(x);
    for (int x : b) bs.insert(x);
    for (int x : a) if (bs.count(x)) ap.push_back(x);
    for (int x : b) if (as.count(x)) bp.push_back(x);
    swap(a, ap);
    swap(b, bp);
}

map<int, int> coordinate_compress(vi& a, vi& b) {
    int cc = 0;
    map<int, int> mp;
    map<int, int> rmp;
    for (int& x : a) {
        if (!mp.count(x)) {
            mp[x] = cc++;
            rmp[mp[x]] = x;
        }
        x = mp[x];
    }
    for (int& x : b) {
        if (!mp.count(x)) {
            mp[x] = cc++;
            rmp[mp[x]] = x;
        }
        x = mp[x];
    }
    return rmp;
}

bool compressed(const vi& a, const vi& b) {
    set<int> as;
    set<int> bs;
    int n = a.size();
    int m = b.size();
    for (int x : a) as.insert(x);
    for (int x : b) bs.insert(x);
    for (int x : a) {
        if (x >= n) return false;
        if (!bs.count(x)) return false;
    }
    for (int x : b) {
        if (x >= m) return false;
        if (!as.count(x)) return false;
    }
    return true;
}

bool is_subsequence(const vi& a, const vi& b) {
    int j = 0;
    for (int x : a) {
        if (j < (int)b.size() && b[j] == x) {
            j++;
        }
    }
    return j == (int)b.size();
}

bool _comp = false;


pair<bool, vi> solve(vi a, vi b) {
    if (!_comp) {
        if (a.empty() || b.empty()) {
            return pair<bool, vi>(true, {});
        }
        if (a.back() == b.back()) {
            vi v;
            while (!a.empty() && !b.empty() && a.back() == b.back()) {
                v.push_back(a.back());
                a.pop_back();
                b.pop_back();
            }
            reverse(v.begin(), v.end());
            auto p = solve(a, b);
            if (p.first) {
                for (int x : v) p.second.push_back(x);
            }
            return p;
        }
        if (a[0] == b[0]) {
            int idx = 0;
            while (idx < (int)min(a.size(), b.size()) && a[idx] == b[idx]) {
                idx++;
            }
            vi ap, bp;
            for (int i=idx; i < (int) a.size(); ++i) ap.push_back(a[i]);
            for (int i=idx; i < (int) b.size(); ++i) bp.push_back(b[i]);
            auto p = solve(ap, bp);
            if (p.first) {
                vi v;
                for (int i=0; i < idx; ++i) v.push_back(a[i]);
                for (int x : p.second) v.push_back(x);
                p.second = v;
            }
            return p;
        }
        if (!compressed(a, b)) {
            clean(a, b);
            if (a.empty() || b.empty()) {
                return pair<bool, vi>(true, {});
            }
            map<int, int> mp = coordinate_compress(a, b);
            _comp = true;
            auto p = solve(a, b);
            if (p.first)
                for (int& x : p.second) x = mp[x];
            return p;
        }
    }

    //End recursive solving part

    vector<function<vi(vi, vi)>> candidates_f = {tomek::ucs, yiping_solexist::ucs, yiping_wa::ucs, felix_wa_jumps::ucs, radewoosh::ucs};

    vi c = candidates_f[0](a, b);
    
    //cerr << "Candidate test" << endl;

    for (auto f : candidates_f) {
        if (c != f(a, b)) return pair<bool, vi>(false, {});
    }

    if (c == vi({-1})) return pair<bool, vi>(false, c);

    return pair<bool, vi>(true, c);
}

vector<int> ucs(vector<int> a, vector<int> b) {
    auto p = solve(a, b);
    if (p.first) {
        return p.second;
    }
    return {-1};
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 38044 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Correct 20 ms 38044 KB Output is correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 18 ms 38080 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 12 ms 38836 KB Output is correct
5 Correct 30 ms 30420 KB Output is correct
6 Correct 198 ms 48972 KB Output is correct
7 Correct 28 ms 40840 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 18 ms 38080 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 12 ms 38836 KB Output is correct
5 Correct 30 ms 30420 KB Output is correct
6 Correct 198 ms 48972 KB Output is correct
7 Correct 28 ms 40840 KB Output is correct
8 Correct 380 ms 83244 KB Output is correct
9 Correct 386 ms 84100 KB Output is correct
10 Correct 378 ms 83372 KB Output is correct
11 Correct 377 ms 83420 KB Output is correct
12 Correct 387 ms 82568 KB Output is correct
13 Correct 537 ms 82764 KB Output is correct
14 Correct 380 ms 82744 KB Output is correct
15 Correct 377 ms 82572 KB Output is correct
16 Correct 384 ms 82748 KB Output is correct
17 Correct 369 ms 81876 KB Output is correct
18 Correct 28 ms 38044 KB Output is correct
19 Correct 22 ms 49300 KB Output is correct
20 Correct 23 ms 38176 KB Output is correct
21 Correct 27 ms 42004 KB Output is correct
22 Correct 175 ms 71040 KB Output is correct
23 Correct 508 ms 77696 KB Output is correct
24 Correct 277 ms 76920 KB Output is correct
25 Correct 283 ms 76840 KB Output is correct
26 Correct 202 ms 70556 KB Output is correct
27 Correct 385 ms 82004 KB Output is correct
28 Correct 381 ms 83340 KB Output is correct
29 Correct 263 ms 51768 KB Output is correct
30 Correct 336 ms 64240 KB Output is correct
31 Correct 424 ms 83636 KB Output is correct
32 Correct 277 ms 50256 KB Output is correct
33 Correct 337 ms 59452 KB Output is correct
34 Correct 245 ms 53456 KB Output is correct
35 Correct 355 ms 82532 KB Output is correct
36 Correct 349 ms 82672 KB Output is correct
37 Correct 354 ms 82712 KB Output is correct
38 Correct 346 ms 82608 KB Output is correct
39 Correct 331 ms 54828 KB Output is correct
40 Correct 323 ms 63976 KB Output is correct
41 Correct 423 ms 82740 KB Output is correct
42 Correct 250 ms 50580 KB Output is correct
43 Correct 320 ms 63324 KB Output is correct
44 Correct 384 ms 82780 KB Output is correct
45 Correct 351 ms 82572 KB Output is correct
46 Correct 338 ms 61052 KB Output is correct
47 Correct 348 ms 82652 KB Output is correct
48 Correct 279 ms 50332 KB Output is correct
49 Correct 270 ms 50232 KB Output is correct
50 Correct 516 ms 82584 KB Output is correct
51 Correct 468 ms 83448 KB Output is correct
52 Correct 380 ms 63416 KB Output is correct
53 Correct 406 ms 84712 KB Output is correct
54 Correct 362 ms 81992 KB Output is correct
55 Correct 334 ms 62676 KB Output is correct
56 Correct 442 ms 82584 KB Output is correct
57 Correct 279 ms 50432 KB Output is correct
58 Correct 349 ms 58628 KB Output is correct
59 Correct 273 ms 50392 KB Output is correct
60 Correct 323 ms 82660 KB Output is correct
61 Correct 330 ms 65916 KB Output is correct
62 Correct 312 ms 58364 KB Output is correct
63 Correct 346 ms 82044 KB Output is correct
64 Correct 245 ms 54392 KB Output is correct
65 Correct 312 ms 59248 KB Output is correct
66 Correct 367 ms 83324 KB Output is correct
67 Correct 386 ms 81948 KB Output is correct
68 Correct 293 ms 58356 KB Output is correct
69 Correct 21 ms 38044 KB Output is correct
70 Correct 16 ms 38044 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 30420 KB Output is correct
2 Correct 24 ms 30552 KB Output is correct
3 Correct 278 ms 71112 KB Output is correct
4 Correct 281 ms 70460 KB Output is correct
5 Correct 270 ms 71800 KB Output is correct
6 Correct 162 ms 67148 KB Output is correct
7 Correct 4 ms 26968 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 3 ms 27104 KB Output is correct
10 Correct 4 ms 26972 KB Output is correct
11 Correct 21 ms 38084 KB Output is correct
12 Correct 22 ms 38044 KB Output is correct
13 Correct 21 ms 38044 KB Output is correct
14 Correct 29 ms 38044 KB Output is correct
15 Correct 27 ms 38104 KB Output is correct
16 Correct 317 ms 69580 KB Output is correct
17 Correct 50 ms 47740 KB Output is correct
18 Correct 218 ms 66784 KB Output is correct
19 Correct 38 ms 42404 KB Output is correct
20 Correct 297 ms 67568 KB Output is correct
21 Correct 48 ms 43728 KB Output is correct
22 Correct 55 ms 47708 KB Output is correct
23 Correct 33 ms 44384 KB Output is correct
24 Correct 72 ms 52248 KB Output is correct
25 Correct 38 ms 43280 KB Output is correct
26 Correct 36 ms 46888 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 83244 KB Output is correct
2 Correct 386 ms 84100 KB Output is correct
3 Correct 378 ms 83372 KB Output is correct
4 Correct 377 ms 83420 KB Output is correct
5 Correct 387 ms 82568 KB Output is correct
6 Correct 537 ms 82764 KB Output is correct
7 Correct 380 ms 82744 KB Output is correct
8 Correct 377 ms 82572 KB Output is correct
9 Correct 384 ms 82748 KB Output is correct
10 Correct 369 ms 81876 KB Output is correct
11 Correct 28 ms 38044 KB Output is correct
12 Correct 22 ms 49300 KB Output is correct
13 Correct 23 ms 38176 KB Output is correct
14 Correct 27 ms 42004 KB Output is correct
15 Correct 175 ms 71040 KB Output is correct
16 Correct 508 ms 77696 KB Output is correct
17 Correct 277 ms 76920 KB Output is correct
18 Correct 283 ms 76840 KB Output is correct
19 Correct 202 ms 70556 KB Output is correct
20 Correct 24 ms 30420 KB Output is correct
21 Correct 24 ms 30552 KB Output is correct
22 Correct 278 ms 71112 KB Output is correct
23 Correct 281 ms 70460 KB Output is correct
24 Correct 270 ms 71800 KB Output is correct
25 Correct 162 ms 67148 KB Output is correct
26 Correct 59 ms 62332 KB Output is correct
27 Correct 45 ms 46400 KB Output is correct
28 Correct 60 ms 62584 KB Output is correct
29 Correct 45 ms 51608 KB Output is correct
30 Correct 27 ms 41112 KB Output is correct
31 Correct 63 ms 58844 KB Output is correct
32 Correct 59 ms 59120 KB Output is correct
33 Correct 54 ms 49720 KB Output is correct
34 Correct 100 ms 65224 KB Output is correct
35 Correct 194 ms 72704 KB Output is correct
36 Correct 171 ms 74616 KB Output is correct
37 Correct 198 ms 73560 KB Output is correct
38 Correct 280 ms 72760 KB Output is correct
39 Correct 214 ms 72788 KB Output is correct
40 Correct 314 ms 78372 KB Output is correct
41 Correct 263 ms 73384 KB Output is correct
42 Correct 155 ms 71160 KB Output is correct
43 Correct 139 ms 69204 KB Output is correct
44 Correct 105 ms 68652 KB Output is correct
45 Correct 118 ms 67340 KB Output is correct
46 Correct 317 ms 77324 KB Output is correct
47 Correct 304 ms 77264 KB Output is correct
48 Correct 290 ms 76556 KB Output is correct
49 Correct 324 ms 76464 KB Output is correct
50 Correct 300 ms 75900 KB Output is correct
51 Correct 289 ms 75788 KB Output is correct
52 Correct 323 ms 75720 KB Output is correct
53 Correct 299 ms 75812 KB Output is correct
54 Correct 286 ms 75040 KB Output is correct
55 Correct 49 ms 50376 KB Output is correct
56 Correct 138 ms 71804 KB Output is correct
57 Correct 141 ms 70424 KB Output is correct
58 Correct 157 ms 72384 KB Output is correct
59 Correct 215 ms 71784 KB Output is correct
60 Correct 278 ms 73484 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Correct 3 ms 27104 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 21 ms 38084 KB Output is correct
6 Correct 22 ms 38044 KB Output is correct
7 Correct 21 ms 38044 KB Output is correct
8 Correct 29 ms 38044 KB Output is correct
9 Correct 27 ms 38104 KB Output is correct
10 Correct 59 ms 62332 KB Output is correct
11 Correct 45 ms 46400 KB Output is correct
12 Correct 60 ms 62584 KB Output is correct
13 Correct 45 ms 51608 KB Output is correct
14 Correct 27 ms 41112 KB Output is correct
15 Correct 63 ms 58844 KB Output is correct
16 Correct 59 ms 59120 KB Output is correct
17 Correct 54 ms 49720 KB Output is correct
18 Correct 61 ms 59756 KB Output is correct
19 Correct 60 ms 57824 KB Output is correct
20 Correct 82 ms 58924 KB Output is correct
21 Correct 57 ms 54364 KB Output is correct
22 Correct 17 ms 38368 KB Output is correct
23 Correct 15 ms 38280 KB Output is correct
24 Correct 17 ms 39192 KB Output is correct
25 Correct 32 ms 55200 KB Output is correct
26 Correct 50 ms 57488 KB Output is correct
27 Correct 71 ms 49876 KB Output is correct
28 Correct 52 ms 53112 KB Output is correct
29 Correct 68 ms 61020 KB Output is correct
30 Correct 57 ms 61476 KB Output is correct
31 Correct 56 ms 60148 KB Output is correct
32 Correct 65 ms 54800 KB Output is correct
33 Correct 16 ms 38076 KB Output is correct
34 Correct 16 ms 38040 KB Output is correct
35 Correct 18 ms 38172 KB Output is correct
36 Correct 15 ms 38300 KB Output is correct
37 Correct 25 ms 38324 KB Output is correct
38 Correct 33 ms 38300 KB Output is correct
39 Correct 25 ms 48540 KB Output is correct
40 Correct 14 ms 38044 KB Output is correct
41 Correct 16 ms 41256 KB Output is correct
42 Correct 47 ms 56548 KB Output is correct
43 Correct 15 ms 38300 KB Output is correct
44 Correct 15 ms 38232 KB Output is correct

Subtask #6
0.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 38044 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Correct 20 ms 38044 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 18 ms 38080 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 12 ms 38836 KB Output is correct
8 Correct 30 ms 30420 KB Output is correct
9 Correct 198 ms 48972 KB Output is correct
10 Correct 28 ms 40840 KB Output is correct
11 Correct 380 ms 83244 KB Output is correct
12 Correct 386 ms 84100 KB Output is correct
13 Correct 378 ms 83372 KB Output is correct
14 Correct 377 ms 83420 KB Output is correct
15 Correct 387 ms 82568 KB Output is correct
16 Correct 537 ms 82764 KB Output is correct
17 Correct 380 ms 82744 KB Output is correct
18 Correct 377 ms 82572 KB Output is correct
19 Correct 384 ms 82748 KB Output is correct
20 Correct 369 ms 81876 KB Output is correct
21 Correct 28 ms 38044 KB Output is correct
22 Correct 22 ms 49300 KB Output is correct
23 Correct 23 ms 38176 KB Output is correct
24 Correct 27 ms 42004 KB Output is correct
25 Correct 175 ms 71040 KB Output is correct
26 Correct 508 ms 77696 KB Output is correct
27 Correct 277 ms 76920 KB Output is correct
28 Correct 283 ms 76840 KB Output is correct
29 Correct 202 ms 70556 KB Output is correct
30 Correct 385 ms 82004 KB Output is correct
31 Correct 381 ms 83340 KB Output is correct
32 Correct 263 ms 51768 KB Output is correct
33 Correct 336 ms 64240 KB Output is correct
34 Correct 424 ms 83636 KB Output is correct
35 Correct 277 ms 50256 KB Output is correct
36 Correct 337 ms 59452 KB Output is correct
37 Correct 245 ms 53456 KB Output is correct
38 Correct 355 ms 82532 KB Output is correct
39 Correct 349 ms 82672 KB Output is correct
40 Correct 354 ms 82712 KB Output is correct
41 Correct 346 ms 82608 KB Output is correct
42 Correct 331 ms 54828 KB Output is correct
43 Correct 323 ms 63976 KB Output is correct
44 Correct 423 ms 82740 KB Output is correct
45 Correct 250 ms 50580 KB Output is correct
46 Correct 320 ms 63324 KB Output is correct
47 Correct 384 ms 82780 KB Output is correct
48 Correct 351 ms 82572 KB Output is correct
49 Correct 338 ms 61052 KB Output is correct
50 Correct 348 ms 82652 KB Output is correct
51 Correct 279 ms 50332 KB Output is correct
52 Correct 270 ms 50232 KB Output is correct
53 Correct 516 ms 82584 KB Output is correct
54 Correct 468 ms 83448 KB Output is correct
55 Correct 380 ms 63416 KB Output is correct
56 Correct 406 ms 84712 KB Output is correct
57 Correct 362 ms 81992 KB Output is correct
58 Correct 334 ms 62676 KB Output is correct
59 Correct 442 ms 82584 KB Output is correct
60 Correct 279 ms 50432 KB Output is correct
61 Correct 349 ms 58628 KB Output is correct
62 Correct 273 ms 50392 KB Output is correct
63 Correct 323 ms 82660 KB Output is correct
64 Correct 330 ms 65916 KB Output is correct
65 Correct 312 ms 58364 KB Output is correct
66 Correct 346 ms 82044 KB Output is correct
67 Correct 245 ms 54392 KB Output is correct
68 Correct 312 ms 59248 KB Output is correct
69 Correct 367 ms 83324 KB Output is correct
70 Correct 386 ms 81948 KB Output is correct
71 Correct 293 ms 58356 KB Output is correct
72 Correct 21 ms 38044 KB Output is correct
73 Correct 16 ms 38044 KB Output is correct
74 Correct 24 ms 30420 KB Output is correct
75 Correct 24 ms 30552 KB Output is correct
76 Correct 278 ms 71112 KB Output is correct
77 Correct 281 ms 70460 KB Output is correct
78 Correct 270 ms 71800 KB Output is correct
79 Correct 162 ms 67148 KB Output is correct
80 Correct 4 ms 26968 KB Output is correct
81 Correct 4 ms 26972 KB Output is correct
82 Correct 3 ms 27104 KB Output is correct
83 Correct 4 ms 26972 KB Output is correct
84 Correct 21 ms 38084 KB Output is correct
85 Correct 22 ms 38044 KB Output is correct
86 Correct 21 ms 38044 KB Output is correct
87 Correct 29 ms 38044 KB Output is correct
88 Correct 27 ms 38104 KB Output is correct
89 Correct 317 ms 69580 KB Output is correct
90 Correct 50 ms 47740 KB Output is correct
91 Correct 218 ms 66784 KB Output is correct
92 Correct 38 ms 42404 KB Output is correct
93 Correct 297 ms 67568 KB Output is correct
94 Correct 48 ms 43728 KB Output is correct
95 Correct 55 ms 47708 KB Output is correct
96 Correct 33 ms 44384 KB Output is correct
97 Correct 72 ms 52248 KB Output is correct
98 Correct 38 ms 43280 KB Output is correct
99 Correct 36 ms 46888 KB Output is correct
100 Correct 59 ms 62332 KB Output is correct
101 Correct 45 ms 46400 KB Output is correct
102 Correct 60 ms 62584 KB Output is correct
103 Correct 45 ms 51608 KB Output is correct
104 Correct 27 ms 41112 KB Output is correct
105 Correct 63 ms 58844 KB Output is correct
106 Correct 59 ms 59120 KB Output is correct
107 Correct 54 ms 49720 KB Output is correct
108 Correct 100 ms 65224 KB Output is correct
109 Correct 194 ms 72704 KB Output is correct
110 Correct 171 ms 74616 KB Output is correct
111 Correct 198 ms 73560 KB Output is correct
112 Correct 280 ms 72760 KB Output is correct
113 Correct 214 ms 72788 KB Output is correct
114 Correct 314 ms 78372 KB Output is correct
115 Correct 263 ms 73384 KB Output is correct
116 Correct 155 ms 71160 KB Output is correct
117 Correct 139 ms 69204 KB Output is correct
118 Correct 105 ms 68652 KB Output is correct
119 Correct 118 ms 67340 KB Output is correct
120 Correct 317 ms 77324 KB Output is correct
121 Correct 304 ms 77264 KB Output is correct
122 Correct 290 ms 76556 KB Output is correct
123 Correct 324 ms 76464 KB Output is correct
124 Correct 300 ms 75900 KB Output is correct
125 Correct 289 ms 75788 KB Output is correct
126 Correct 323 ms 75720 KB Output is correct
127 Correct 299 ms 75812 KB Output is correct
128 Correct 286 ms 75040 KB Output is correct
129 Correct 49 ms 50376 KB Output is correct
130 Correct 138 ms 71804 KB Output is correct
131 Correct 141 ms 70424 KB Output is correct
132 Correct 157 ms 72384 KB Output is correct
133 Correct 215 ms 71784 KB Output is correct
134 Correct 278 ms 73484 KB Output is correct
135 Correct 61 ms 59756 KB Output is correct
136 Correct 60 ms 57824 KB Output is correct
137 Correct 82 ms 58924 KB Output is correct
138 Correct 57 ms 54364 KB Output is correct
139 Correct 17 ms 38368 KB Output is correct
140 Correct 15 ms 38280 KB Output is correct
141 Correct 17 ms 39192 KB Output is correct
142 Correct 32 ms 55200 KB Output is correct
143 Correct 50 ms 57488 KB Output is correct
144 Correct 71 ms 49876 KB Output is correct
145 Correct 52 ms 53112 KB Output is correct
146 Correct 68 ms 61020 KB Output is correct
147 Correct 57 ms 61476 KB Output is correct
148 Correct 56 ms 60148 KB Output is correct
149 Correct 65 ms 54800 KB Output is correct
150 Correct 16 ms 38076 KB Output is correct
151 Correct 16 ms 38040 KB Output is correct
152 Correct 18 ms 38172 KB Output is correct
153 Correct 15 ms 38300 KB Output is correct
154 Correct 25 ms 38324 KB Output is correct
155 Correct 33 ms 38300 KB Output is correct
156 Correct 25 ms 48540 KB Output is correct
157 Correct 14 ms 38044 KB Output is correct
158 Correct 16 ms 41256 KB Output is correct
159 Correct 47 ms 56548 KB Output is correct
160 Correct 15 ms 38300 KB Output is correct
161 Correct 15 ms 38232 KB Output is correct
162 Correct 148 ms 70972 KB Output is correct
163 Correct 43 ms 63564 KB Output is correct
164 Incorrect 88 ms 64416 KB Output isn't correct
165 Halted 0 ms 0 KB -