Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
正整数からなる集合 S について、任意の a,\ b \in S\ (a\neq b) について b が a の倍数でないとき、 S を「良い集合」と呼びます。
N 個の 1 以上 2M 以下の整数からなる集合 S=\lbrace A_1,\ A_2,\ \dots,\ A_N\rbrace が与えられます。
各 i=1,\ 2,\ \dots,\ N に対し、A_i を含む S の部分集合であって、要素数が M である「良い集合」が存在するか判定してください。
制約
- M \leq N \leq 2M
- 1 \leq M \leq 3 \times 10^5
- 1 \leq A_1 < A_2 < \dots < A_N \leq 2M
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N M A_1 A_2 \dots A_{N}
出力
N 行出力してください。 i 行目には A_i を含む S の部分集合であって、要素数が M である「良い集合」が存在する場合 Yes
を、存在しない場合 No
を出力してください。
入力例 1
5 3 1 2 3 4 5
出力例 1
No Yes Yes Yes Yes
A_1=1 を含む「良い集合」は明らかに \lbrace 1\rbrace しか存在せず、要素数は 1 しかないため、i=1 に対する答えは No
です。
A_2=2 を含む「良い集合」としては例えば \lbrace 2,\ 3,\ 5\rbrace が考えられます。このことから i=2 に対する答えは Yes
です。
入力例 2
4 4 2 4 6 8
出力例 2
No No No No
入力例 3
13 10 2 3 4 6 7 9 10 11 13 15 17 19 20
出力例 3
No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No
Score : 700 points
Problem Statement
We say that a set S of positive integers is good when, for any a,\ b \in S\ (a\neq b), b is not a multiple of a.
You are given a set of N integers between 1 and 2M (inclusive): S=\lbrace A_1,\ A_2,\ \dots,\ A_N\rbrace.
For each i=1,\ 2,\ \dots,\ N, determine whether there exists a good set with M elements that is a subset of S containing A_i.
Constraints
- M \leq N \leq 2M
- 1 \leq M \leq 3 \times 10^5
- 1 \leq A_1 < A_2 < \dots < A_N \leq 2M
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_{N}
Output
Print N lines. The i-th line should contain Yes
if there exists a good set with M elements that is a subset of S containing A_i, and No
otherwise.
Sample Input 1
5 3 1 2 3 4 5
Sample Output 1
No Yes Yes Yes Yes
Trivially, the only good set containing A_1=1 is \lbrace 1\rbrace, which has just one element, so the answer for i=1 is No
.
There is a good set \lbrace 2,\ 3,\ 5\rbrace containing A_2=2, so the answer for i=2 is Yes
.
Sample Input 2
4 4 2 4 6 8
Sample Output 2
No No No No
Sample Input 3
13 10 2 3 4 6 7 9 10 11 13 15 17 19 20
Sample Output 3
No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No