hieroglyphs — IOI contest
Task type: batch | Time limit: 1 s | Memory limit: 2048 MB | Difficulty: 28
Algorithms: greedy, dynamic programming, ad-hoc, data structures, segment tree

# Hieroglyphs

A team of researchers is studying the similarities between sequences of hieroglyphs.
They represent each hieroglyph with a non-negative integer.
To perform their study,
 they use the following concepts about sequences.

For a fixed sequence $A$,
 a sequence $S$ is called a **subsequence** of $A$
 if and only if $S$ can be obtained
 by removing some elements (possibly none) from $A$.

The table below shows some examples of subsequences of a sequence $A = [3, 2, 1, 2]$.

| Subsequence    | How it can be obtained from $A$ |
|----------------|---------------------------------|
| [3, 2, 1, 2] | No elements are removed.
| [2, 1, 2]     | [
3
, 2, 1, 2]
| [3, 2, 2]     | [3, 2, 
1
, 2]
| [3, 2]         | [3, 
2
, 
1
, 2] or [3, 2, 
1
, 
2
]
| [3]             | [3, 
2
, 
1
, 
2
]
| [ ]              | [
3
, 
2
, 
1
, 
2
]

On the other hand, $[3, 3]$ or $[1, 3]$ are not subsequences of $A$.

Consider two sequences of hieroglyphs, $A$ and $B$.
A sequence $S$ is called a **common subsequence** of $A$ and $B$
 if and only if $S$ is a subsequence of both $A$ and $B$.
Moreover, we say that a sequence $U$ is a **universal common subsequence** of $A$ and $B$
 if and only if the following two conditions are met:
* $U$ is a common subsequence of $A$ and $B$.
* Every common subsequence of $A$ and $B$ is also a subsequence of $U$.

It can be shown that any two sequences $A$ and $B$
 have at most one universal common subsequence.

The researchers have found two sequences of hieroglyphs $A$ and $B$.
Sequence $A$ consists of $N$ hieroglyphs
 and sequence $B$ consists of $M$ hieroglyphs.
Help the researchers compute
 a universal common subsequence of sequences $A$ and $B$,
 or determine that such a sequence does not exist.

## Implementation details

You should implement the following procedure.

```
std::vector&lt;int&gt; ucs(std::vector&lt;int&gt; A, std::vector&lt;int&gt; B)
```

* $A$: array of length $N$ describing the first sequence.
* $B$: array of length $M$ describing the second sequence.
* If there exists a universal common subsequence of $A$ and $B$,
   the procedure should return an array containing this sequence.
  Otherwise, the procedure should return $[-1]$
   (an array of length $1$, whose only element is $-1$).
* This procedure is called exactly once for each test case.

## Constraints

* $1 \leq N \leq 100\,000$
* $1 \leq M \leq 100\,000$
* $0 \leq A[i] \leq 200\,000$ for each $i$ such that $0 \leq i < N$
* $0 \leq B[j] \leq 200\,000$ for each $j$ such that $0 \leq j < M$

## Subtasks

| Subtask | Score  | Additional Constraints |
| :-----: | :----: | ---------------------- |
| 1       | $3$    | $N = M$; each of $A$ and $B$ consists of $N$ **distinct** integers between $0$ and $N-1$ (inclusive)
| 2       | $15$   | For any integer $k$, (the number of elements of $A$ equal to $k$) plus (the number of elements of $B$ equal to $k$) is at most $3$.
| 3       | $10$   | $A[i] \leq 1$ for each $i$ such that $0 \leq i < N$; $B[j] \leq 1$ for each $j$ such that $0 \leq j < M$
| 4       | $16$   | There exists a universal common subsequence of $A$ and $B$.
| 5       | $14$   | $N \leq 3000$; $M \leq 3000$
| 6       | $42$   | No additional constraints.

## Examples

### Example 1

Consider the following call.

```
ucs([0, 0, 1, 0, 1, 2], [2, 0, 1, 0, 2])
```

Here, the common subsequences of $A$ and $B$ are the following:
 $[\ ]$, $[0]$, $[1]$, $[2]$, $[0, 0]$, $[0, 1]$, $[0, 2]$, $[1, 0]$, $[1, 2]$, $[0, 0, 2]$, $[0, 1, 0]$, $[0, 1, 2]$, $[1, 0, 2]$ and $[0, 1, 0, 2]$.

Since $[0, 1, 0, 2]$ is a common subsequence of $A$ and $B$, and
 all common subsequences of $A$ and $B$ are subsequences of $[0, 1, 0, 2]$,
 the procedure should return $[0, 1, 0, 2]$.

### Example 2

Consider the following call.

```
ucs([0, 0, 2], [1, 1])
```

Here, the only common subsequence of $A$ and $B$ is the empty sequence $[\ ]$.
It follows that the procedure should return an empty array $[\ ]$.

### Example 3

Consider the following call.
```
ucs([0, 1, 0], [1, 0, 1])
```

Here, the common subsequences of $A$ and $B$ are
 $[\ ], [0], [1], [0, 1]$ and $[1, 0]$.
It can be shown that a universal common subsequence does not exist.
Therefore, the procedure should return $[-1]$.

## Sample Grader

Input format:

```
N  M
A[0]  A[1]  ...  A[N-1]
B[0]  B[1]  ...  B[M-1]
```

Output format:

```
T
R[0]  R[1]  ...  R[T-1]
```

Here, $R$ is the array returned by `ucs` and $T$ is its length.


Starter code:
grader.cpp: #include "hieroglyphs.h"
#include <cassert>
#include <cstdio>
#include <vector>

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;
}

hieroglyphs.h: #include <vector>

std::vector<int> ucs(std::vector<int> A, std::vector<int> B);

hieroglyphs.cpp: #include "hieroglyphs.h"
#include <vector>

std::vector<int> ucs(std::vector<int> A, std::vector<int> B) {
  return std::vector<int>();
}