Hieroglyphs

hieroglyphs
English (ISC)
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.
hieroglyphs (1 of 3)

Implementation details
You should implement the following procedure.
std::vector ucs(std::vector A, std::vector 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 ≤N ≤100 000
1 ≤M ≤100 000
0 ≤A[i] ≤200 000 for each i such that 0 ≤i < N
0 ≤B[j] ≤200 000 for each j such that 0 ≤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] ≤1 for each i such that 0 ≤i < N; B[j] ≤1 for each j such that
0 ≤j < M
4
16
There exists a universal common subsequence of A and B.
5
14
N ≤3000; M ≤3000
6
42
No additional constraints.
Examples
Example 1
Consider the following call.
hieroglyphs (2 of 3)

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.
hieroglyphs (3 of 3)

Input / Output on this judge

This is the IOI function-implementation task hieroglyphs adapted to standard input / output. Instead of implementing the function, read its arguments from standard input and print the returned value(s) to standard output, exactly as the official grader below does (its internal anti-cheat checks have been removed). You may also simply submit the grader together with your own implementation of the function.

Function signature (hieroglyphs.h):

#include <vector>

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

Reference I/O driver (official grader, sanitized):

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

rip 작성

출처 IOI 2024