E - Cards Query Problem

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 から N までの番号がついた N 個の空の箱と、何も書かれていない無数のカードがあります。
Q 個のクエリが与えられるので、順番に処理してください。クエリは次の 3 種類のいずれかです。

  • 1 i j \colon カードを 1 枚選んで数 i を書き込み、そのカードを箱 j に入れる
  • 2 i \colon 箱 i に入っているカードに書かれた数を昇順ですべて答える
  • 3 i \colon 数 i が書かれたカードが入っている箱の番号を昇順ですべて答える

ただし、以下の点に注意してください。

  • 2 番目の形式のクエリにおいては、箱 i の中に同じ数が書かれたカードが複数枚あるときは、入っている枚数と同じ回数だけその数を出力する
  • 3 番目の形式のクエリにおいては、数 i が書かれたカードが同じ箱に複数枚入っている場合でも、その箱の番号は 1 度だけ出力する

制約

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 番目の形式のクエリについて、
    • 1 \leq i \leq 2 \times 10^5
    • 1 \leq j \leq N
  • 2 番目の形式のクエリについて、
    • 1 \leq i \leq N
    • このクエリが与えられる時点で箱 i にカードが入っている
  • 3 番目の形式のクエリについて、
    • 1 \leq i \leq 2 \times 10^5
    • このクエリが与えられる時点で数 i が書かれたカードが入っている箱が存在する
  • 出力するべき数は合計で 2 \times 10^5 個以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

ただし、\mathrm{query}_q は q 個目のクエリを表しており、次のいずれかの形式で与えられる。

1 i j

2 i

3 i

出力

2 番目の形式のクエリと 3 番目の形式のクエリに対し、順番に答えを出力せよ。
各クエリでは出力するべき要素を昇順に空白区切りで出力し、クエリごとに改行せよ。

入力例 1

5
8
1 1 1
1 2 4
1 1 4
2 4
1 1 4
2 4
3 1
3 2

出力例 1

1 2
1 1 2
1 4
4

クエリを順に処理していきます。

  • カードに 1 を書き込み、箱 1 に入れます。
  • カードに 2 を書き込み、箱 4 に入れます。
  • カードに 1 を書き込み、箱 4 に入れます。
  • 箱 4 に入っているカードに書かれた数は 1, 2 です。
    • 1, 2 の順に出力してください。
  • カードに 1 を書き込み、箱 4 に入れます。
  • 箱 4 に入っているカードに書かれた数は 1, 1, 2 です。
    • 1 を 2 度出力することに注意してください。
  • 数 1 が書かれたカードが入っている箱は箱 1, 4 です。
    • 箱 4 には数 1 が書かれたカードが 2 枚入っていますが、4 は 1 回しか出力しないことに注意してください。
  • 数 2 が書かれたカードが入っている箱は箱 4 です。

入力例 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

出力例 2

1 2 200000
1

Score : 300 points

Problem Statement

We have N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

  • 1 i j \colon Write the number i on a blank card and put it into box j.
  • 2 i \colon Report all numbers written on the cards in box i, in ascending order.
  • 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

  • In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
  • In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

  • 1 \leq N, Q \leq 2 \times 10^5
  • For a query of the first kind:
    • 1 \leq i \leq 2 \times 10^5
    • 1 \leq j \leq N
  • For a query of the second kind:
    • 1 \leq i \leq N
    • Box i contains some cards when this query is given.
  • For a query of the third kind:
    • 1 \leq i \leq 2 \times 10^5
    • Some boxes contain a card with the number i when this query is given.
  • At most 2 \times 10^5 numbers are to be reported.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Here, \mathrm{query}_q denotes the q-th query, which is in one of the following formats:

1 i j

2 i

3 i

Output

Respond to the queries of the second and third kinds in order.
For each of those queries, print one line containing the elements to be reported in ascending order, with spaces in between.

Sample Input 1

5
8
1 1 1
1 2 4
1 1 4
2 4
1 1 4
2 4
3 1
3 2

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

  • Write 1 on a card and put it into box 1.
  • Write 2 on a card and put it into box 4.
  • Write 1 on a card and put it into box 4.
  • Box 4 contains cards with the numbers 1 and 2.
    • Print 1 and 2 in this order.
  • Write 1 on a card and put it into box 4.
  • Box 4 contains cards with the numbers 1, 1, and 2.
    • Note that you should print 1 twice.
  • Boxes 1 and 4 contain a card with the number 1.
    • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
  • Boxes 4 contains a card with the number 2.

Sample Input 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

Sample Output 2

1 2 200000
1
F - Max MEX

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の非負整数列 A が与えられます。
A から K 要素を選んで順序を保ったまま抜き出した列を B としたとき、 MEX(B) としてありえる最大値を求めてください。

但し、数列 X に対して MEX(X) は以下の条件を満たす唯一の非負整数 m として定義されます。

  • 0 \le i < m を満たす全ての整数 i が X に含まれる。
  • m が X に含まれない。

制約

  • 入力は全て整数
  • 1 \le K \le N \le 3 \times 10^5
  • 0 \le A_i \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

7 3
2 0 2 3 2 1 9

出力例 1

3

この入力では A=(2,0,2,3,2,1,9) であり、ここから K=3 要素を選んで抜き出して数列 B を得ます。例えば、

  • 1,2,3 要素目を抜き出した時、 MEX(B)=MEX(2,0,2)=1
  • 3,4,6 要素目を抜き出した時、 MEX(B)=MEX(2,3,1)=0
  • 2,6,7 要素目を抜き出した時、 MEX(B)=MEX(0,1,9)=2
  • 2,3,6 要素目を抜き出した時、 MEX(B)=MEX(0,2,1)=3

のようになります。
達成可能な MEX の最大値は 3 です。

Score : 300 points

Problem Statement

You are given a length-N sequence of non-negative integers.
When B is a sequence obtained by choosing K elements from A and concatenating them without changing the order, find the maximum possible value of MEX(B).

Here, for a sequence X, we define MEX(X) as the unique non-negative integer m that satisfies the following conditions:

  • Every integer i such that 0 \le i < m is contained in X.
  • m is not contained in X.

Constraints

  • All values in the input are integers.
  • 1 \le K \le N \le 3 \times 10^5
  • 0 \le A_i \le 10^9

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

7 3
2 0 2 3 2 1 9

Sample Output 1

3

In this input, A=(2,0,2,3,2,1,9), and you obtain the sequence B by picking K=3 elements. For example,

  • If the 1-st, 2-nd, and 3-rd elements are chosen, MEX(B)=MEX(2,0,2)=1.
  • If the 3-rd, 4-th, and 6-th elements are chosen, MEX(B)=MEX(2,3,1)=0.
  • If the 2-nd, 6-th, and 7-th elements are chosen, MEX(B)=MEX(0,1,9)=2.
  • If the 2-nd, 3-rd, and 6-th elements are chosen, MEX(B)=MEX(0,2,1)=3.

The maximum possible MEX is 3.
G - Swap Hats

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

1, 2, 3 の番号がついた 3 人の高橋くんがおり、赤・緑・青の色がついた 3 種類の帽子がそれぞれ 1 つずつあります。それぞれの高橋くんは帽子を 1 つかぶっており、高橋くん i がはじめにかぶっている帽子の色は文字 S_i で表されます。ここで、R は赤、G は緑、B は青に対応しています。これから、以下の操作をちょうど 10^{18} 回行います。

操作

  • 3 人の高橋くんのうち 2 人を選ぶ。2 人はお互いのかぶっている帽子を交換する。

10^{18} 回の操作の後、高橋くん i が文字 T_i に対応する色の帽子をかぶっているようにすることはできますか？

制約

  • S_1, S_2, S_3 は R, G, B の並べ替えである
  • T_1, T_2, T_3 は R, G, B の並べ替えである

入力

入力は以下の形式で標準入力から与えられる。

S_1 S_2 S_3
T_1 T_2 T_3

出力

10^{18} 回の操作の後、高橋くん i が文字 T_i に対応する色の帽子をかぶっているようにすることはできる場合は Yes を、できない場合は No を出力せよ。

入力例 1

R G B
R G B

出力例 1

Yes

例えば、高橋くん 1 と高橋くん 2 の帽子を交換する操作を 10^{18} 回行うと目的を達成できます。

Score : 400 points

Problem Statement

There are three Takahashis numbered 1, 2 and 3, and three hats colored red, green, and blue. Each Takahashi is wearing one hat. The color of the hat that Takahashi i is currently wearing is represented by a character S_i. Here, R corresponds to red, G to green, and B to blue. Now, they will do the following operation exactly 10^{18} times.

Operation

  • Choose two out of the three Takahashis. The two exchange the hats they are wearing.

Is it possible to make Takahashi i wearing the hat of color corresponding to character T_i after the 10^{18} repetitions?

Constraints

  • S_1, S_2, S_3 are a permutation of R, G, B.
  • T_1, T_2, T_3 are a permutation of R, G, B.

Input

Input is given from Standard Input in the following format:

S_1 S_2 S_3
T_1 T_2 T_3

Output

If it is possible to make Takahashi i wearing the hat of color corresponding to character T_i after the 10^{18} repetitions, print Yes; otherwise, print No.

Sample Input 1

R G B
R G B

Sample Output 1

Yes

For example, the objective can be achieved by repeating 10^{18} times the operation of swapping the hats of Takahashi 1 and Takahashi 2.
H - Kth Number

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

0 以上 M 以下の整数からなる長さ N の数列 A=(A_1,A_2,\dots,A_N) があります。

今からすぬけくんが以下の操作 1, 2 を順に行います。

  1. A_i=0 を満たすそれぞれの i について、1 以上 M 以下の整数を独立かつ一様ランダムに選び、A_i をその整数で置き換える。
  2. A を昇順に並び替える。

すぬけくんが操作 1, 2 を行ったあとの A_K の期待値を \text{mod } 998244353 で出力してください。

「期待値を \text{mod } 998244353 で出力」とは 求める期待値は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、 R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ 1 つ存在することが証明できます。この R を出力してください。

制約

  • 1\leq K \leq N \leq 2000
  • 1\leq M \leq 2000
  • 0\leq A_i \leq M
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M K
A_1 A_2 \dots A_N

出力

すぬけくんが操作 1, 2 を行ったあとの A_K の期待値を \text{mod } 998244353 で出力せよ。

入力例 1

3 5 2
2 0 4

出力例 1

3

すぬけくんは操作 1 において A_2 を 1 以上 5 以下の整数で置き換えます。この整数を x とすると、

  • x=1,2 のとき、すぬけくんが操作 1, 2 を行ったあと A_2=2 です。
  • x=3 のとき、すぬけくんが操作 1, 2 を行ったあと A_2=3 です。
  • x=4,5 のとき、すぬけくんが操作 1, 2 を行ったあと A_2=4 です。

よって、A_2 の期待値は \frac{2+2+3+4+4}{5}=3 です。

入力例 2

2 3 1
0 0

出力例 2

221832080

期待値は \frac{14}{9} です。

入力例 3

10 20 7
6 5 0 2 0 0 0 15 0 0

出力例 3

617586310

Score : 500 points

Problem Statement

We have a sequence of length N consisting of integers between 0 and M, inclusive: A=(A_1,A_2,\dots,A_N).

Snuke will perform the following operations 1 and 2 in order.

  1. For each i such that A_i=0, independently choose a uniform random integer between 1 and M, inclusive, and replace A_i with that integer.
  2. Sort A in ascending order.

Print the expected value of A_K after the two operations, modulo 998244353.

How to print a number modulo 998244353? It can be proved that the sought expected value is always rational. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} using two coprime integers P and Q, it can be proved that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print this R.

Constraints

  • 1\leq K \leq N \leq 2000
  • 1\leq M \leq 2000
  • 0\leq A_i \leq M
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M K
A_1 A_2 \dots A_N

Output

Print the expected value of A_K after the two operations, modulo 998244353.

Sample Input 1

3 5 2
2 0 4

Sample Output 1

3

In the operation 1, Snuke will replace A_2 with an integer between 1 and 5. Let x be this integer.

  • If x=1 or 2, we will have A_2=2 after the two operations.
  • If x=3, we will have A_2=3 after the two operations.
  • If x=4 or 5, we will have A_2=4 after the two operations.

Thus, the expected value of A_2 is \frac{2+2+3+4+4}{5}=3.

Sample Input 2

2 3 1
0 0

Sample Output 2

221832080

The expected value is \frac{14}{9}.

Sample Input 3

10 20 7
6 5 0 2 0 0 0 15 0 0

Sample Output 3

617586310
I - Vacation Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

0, 1 からなる長さ N の文字列 S が与えられます。S の i 文字目を S_i とします。

Q 個のクエリを与えられた順に処理してください。
クエリは 3 個の整数の組 (c, L, R) で表されて、c の値によってクエリの種類が異なります。

  • c=1 のとき : L \leq i \leq R を満たす整数 i について、S_i が 1 ならば 0 に、0 ならば 1 に変更する。
  • c=2 のとき : S の L 文字目から R 文字目までを取り出して出来る文字列を T とする。T に含まれる連続する 1 の長さの最大値を出力する。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq Q \leq 10^5
  • S は長さ N の 0, 1 からなる文字列
  • c \in \lbrace 1, 2 \rbrace
  • 1 \leq L \leq R \leq N
  • N, Q, c, L, R は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは次の形式で与えられる。

c L R

出力

c=2 であるクエリの個数を k として、k 行出力せよ。
i 行目には i 番目の c=2 であるクエリに対する答えを出力せよ。

入力例 1

7 6
1101110
2 1 7
2 2 4
1 3 6
2 5 6
1 4 7
2 1 7

出力例 1

3
1
0
7

クエリを順に処理すると次のようになります。

  • はじめ、S= 1101110 です。
  • 1 番目のクエリについて、T = 1101110 です。T に含まれる連続する 1 の中で最も長いものは、T の 4 文字目から 6 文字目からなる 111 なので、答えは 3 になります。
  • 2 番目のクエリについて、T = 101 です。T に含まれる連続する 1 の中で最も長いものは、T の 1 文字目あるいは 3 文字目の 1 なので、答えは 1 になります。
  • 3 番目のクエリについて、操作後の S は 1110000 です。
  • 4 番目のクエリについて、T = 00 です。T に 1 は含まれないので答えは 0 になります。
  • 5 番目のクエリについて、操作後の S は 1111111 です。
  • 6 番目のクエリについて、T = 1111111 です。T に含まれる連続する 1 の中で最も長いものは、T の 1 文字目から 7 文字目からなる 1111111 なので、答えは 7 になります。

Score : 550 points

Problem Statement

You are given a string S of length N consisting of 0 and 1. Let S_i denote the i-th character of S.

Process Q queries in the order they are given.
Each query is represented by a tuple of three integers (c, L, R), where c represents the type of the query.

  • When c=1: For each integer i such that L \leq i \leq R, if S_i is 1, change it to 0; if it is 0, change it to 1.
  • When c=2: Let T be the string obtained by extracting the L-th through R-th characters of S. Print the maximum number of consecutive 1s in T.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq Q \leq 10^5
  • S is a string of length N consisting of 0 and 1.
  • c \in \lbrace 1, 2 \rbrace
  • 1 \leq L \leq R \leq N
  • N, Q, c, L, and R are all integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i represents the i-th query:

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

c L R

Output

Let k be the number of queries with c=2. Print k lines.
The i-th line should contain the answer to the i-th query with c=2.

Sample Input 1

7 6
1101110
2 1 7
2 2 4
1 3 6
2 5 6
1 4 7
2 1 7

Sample Output 1

3
1
0
7

The queries are processed as follows.

  • Initially, S= 1101110.
  • For the first query, T = 1101110. The longest sequence of consecutive 1s in T is 111 from the 4-th character to 6-th character, so the answer is 3.
  • For the second query, T = 101. The longest sequence of consecutive 1s in T is 1 at the 1-st or 3-rd character, so the answer is 1.
  • For the third query, the operation changes S to 1110000.
  • For the fourth query, T = 00. T does not contain 1, so the answer is 0.
  • For the fifth query, the operation changes S to 1111111.
  • For the sixth query, T = 1111111. The longest sequence of consecutive 1s in T is 1111111 from the 1-st to 7-th characters, so the answer is 7.