A9816. Chicken or Fish?
编程题
普及/提高-
知识点
题目描述
Each test in this problem consists of one or more input sets. First goes a string that contains a single integer $t$ ( $1<=t<=100000$ ) — the number of input data sets in the test. Then the sets follow, each set is preceded by an empty line.
The first line of each set of the input contains integers $m$ , $k$ ( $2<=m<=100000$ , $1<=k<=100000$ ) — the number of Polycarp's seat and the number of dishes, respectively.
The second line contains a sequence of $k$ integers $a_{1},a_{2},...,a_{k}$ ( $1<=a_{i}<=100000$ ), where $a_{i}$ is the initial number of portions of the $i$ -th dish.
Then $m-1$ lines follow, each line contains the description of Polycarp's observations about giving food to a passenger sitting in front of him: the $j$ -th line contains a pair of integers $t_{j},r_{j}$ ( $0<=t_{j}<=k,0<=r_{j}<=1$ ), where $t_{j}$ is the number of the dish that was given to the $j$ -th passenger (or 0, if Polycarp didn't notice what dish was given to the passenger), and $r_{j}$ — a 1 or a 0, depending on whether the $j$ -th passenger was or wasn't disappointed, respectively.
We know that sum $a_{i}$ equals at least $m$ , that is,Polycarp will definitely get some dish, even if it is the last thing he wanted. It is guaranteed that the data is consistent.
Sum $m$ for all input sets doesn't exceed $100000$ . Sum $k$ for all input sets doesn't exceed $100000$ .
The first line of each set of the input contains integers $m$ , $k$ ( $2<=m<=100000$ , $1<=k<=100000$ ) — the number of Polycarp's seat and the number of dishes, respectively.
The second line contains a sequence of $k$ integers $a_{1},a_{2},...,a_{k}$ ( $1<=a_{i}<=100000$ ), where $a_{i}$ is the initial number of portions of the $i$ -th dish.
Then $m-1$ lines follow, each line contains the description of Polycarp's observations about giving food to a passenger sitting in front of him: the $j$ -th line contains a pair of integers $t_{j},r_{j}$ ( $0<=t_{j}<=k,0<=r_{j}<=1$ ), where $t_{j}$ is the number of the dish that was given to the $j$ -th passenger (or 0, if Polycarp didn't notice what dish was given to the passenger), and $r_{j}$ — a 1 or a 0, depending on whether the $j$ -th passenger was or wasn't disappointed, respectively.
We know that sum $a_{i}$ equals at least $m$ , that is,Polycarp will definitely get some dish, even if it is the last thing he wanted. It is guaranteed that the data is consistent.
Sum $m$ for all input sets doesn't exceed $100000$ . Sum $k$ for all input sets doesn't exceed $100000$ .
输入格式
For each input set print the answer as a single line. Print a string of $k$ letters "Y" or "N". Letter "Y" in position $i$ should be printed if they could have run out of the $i$ -th dish by the time the stewardess started serving Polycarp.
输出格式
In the first input set depending on the choice of the second passenger the situation could develop in different ways:
- If he chose the first dish, then by the moment the stewardess reaches Polycarp, they will have run out of the first dish;
- If he chose the fourth dish, then by the moment the stewardess reaches Polycarp, they will have run out of the fourth dish;
- Otherwise, Polycarp will be able to choose from any of the four dishes.
Thus, the answer is "YNNY".
In the second input set there is, for example, the following possible scenario. First, the first passenger takes the only third dish, then the second passenger takes the second dish. Then, the third passenger asks for the third dish, but it is not available, so he makes disappointed muttering and ends up with the second dish. Then the fourth passenger takes the fourth dish, and Polycarp ends up with the choice between the first, fourth and fifth dish.
Likewise, another possible scenario is when by the time the stewardess comes to Polycarp, they will have run out of either the first or the fifth dish (this can happen if one of these dishes is taken by the second passenger). It is easy to see that there is more than enough of the fourth dish, so Polycarp can always count on it. Thus, the answer is "YYYNY".
- If he chose the first dish, then by the moment the stewardess reaches Polycarp, they will have run out of the first dish;
- If he chose the fourth dish, then by the moment the stewardess reaches Polycarp, they will have run out of the fourth dish;
- Otherwise, Polycarp will be able to choose from any of the four dishes.
Thus, the answer is "YNNY".
In the second input set there is, for example, the following possible scenario. First, the first passenger takes the only third dish, then the second passenger takes the second dish. Then, the third passenger asks for the third dish, but it is not available, so he makes disappointed muttering and ends up with the second dish. Then the fourth passenger takes the fourth dish, and Polycarp ends up with the choice between the first, fourth and fifth dish.
Likewise, another possible scenario is when by the time the stewardess comes to Polycarp, they will have run out of either the first or the fifth dish (this can happen if one of these dishes is taken by the second passenger). It is easy to see that there is more than enough of the fourth dish, so Polycarp can always count on it. Thus, the answer is "YYYNY".
输入输出样例
输入 #1
2 3 4 2 3 2 1 1 0 0 0 5 5 1 2 1 3 1 3 0 0 0 2 1 4 0
输出 #1
YNNY YYYNY
说明/提示
In the first input set depending on the choice of the second passenger the situation could develop in different ways:
- If he chose the first dish, then by the moment the stewardess reaches Polycarp, they will have run out of the first dish;
- If he chose the fourth dish, then by the moment the stewardess reaches Polycarp, they will have run out of the fourth dish;
- Otherwise, Polycarp will be able to choose from any of the four dishes.
Thus, the answer is "YNNY".
In the second input set there is, for example, the following possible scenario. First, the first passenger takes the only third dish, then the second passenger takes the second dish. Then, the third passenger asks for the third dish, but it is not available, so he makes disappointed muttering and ends up with the second dish. Then the fourth passenger takes the fourth dish, and Polycarp ends up with the choice between the first, fourth and fifth dish.
Likewise, another possible scenario is when by the time the stewardess comes to Polycarp, they will have run out of either the first or the fifth dish (this can happen if one of these dishes is taken by the second passenger). It is easy to see that there is more than enough of the fourth dish, so Polycarp can always count on it. Thus, the answer is "YYYNY".
- If he chose the first dish, then by the moment the stewardess reaches Polycarp, they will have run out of the first dish;
- If he chose the fourth dish, then by the moment the stewardess reaches Polycarp, they will have run out of the fourth dish;
- Otherwise, Polycarp will be able to choose from any of the four dishes.
Thus, the answer is "YNNY".
In the second input set there is, for example, the following possible scenario. First, the first passenger takes the only third dish, then the second passenger takes the second dish. Then, the third passenger asks for the third dish, but it is not available, so he makes disappointed muttering and ends up with the second dish. Then the fourth passenger takes the fourth dish, and Polycarp ends up with the choice between the first, fourth and fifth dish.
Likewise, another possible scenario is when by the time the stewardess comes to Polycarp, they will have run out of either the first or the fifth dish (this can happen if one of these dishes is taken by the second passenger). It is easy to see that there is more than enough of the fourth dish, so Polycarp can always count on it. Thus, the answer is "YYYNY".