/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
長さ N の正整数列 A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N) が与えられます。
以下の条件を全て満たす整数列 X=(X_1,X_2,\ldots,X_N) が存在するか判定し、存在するなら一つ求めてください。
- -10^8\le X_i\le 10^8 (1\le i\le N)
- \displaystyle \sum_{i=1}^N A_iX_i > 0
- \displaystyle \sum_{i=1}^N B_iX_i < 0
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 2\times 10^5
- 1\le N\le 2\times 10^5
- 1\le A_i,B_i\le 10^5
- 全てのテストケースにおける N の総和は 2\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、条件を全て満たす X が存在しない場合は No と出力せよ。
そうでない場合、条件を全て満たす X を以下の形式で出力せよ。
Yes X_1 X_2 \ldots X_N
条件を満たす X が複数ある場合、どれを出力しても正答となる。
入力例 1
3 3 3 1 4 1 5 1 3 4 4 4 7 7 7 4 20 25 6 15 31 41 59 26
出力例 1
Yes 4 -5 1 No Yes 45 -10 -40 11
1 つ目のテストケースについて、 X=(4,-5,1) とすると
- \displaystyle \sum_{i=1}^3 A_iX_i=3\times 4+1\times (-5)+4\times 1=11>0
- \displaystyle \sum_{i=1}^3 B_iX_i=1\times 4+5\times (-5)+1\times 1=-20<0
となり条件を満たします。この他にも X=(3,-3,1) や X=(27,-40,22) などが条件を満たします。
Score : 500 points
Problem Statement
You are given sequences of positive integers of length N: A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N).
Determine whether there exists an integer sequence X=(X_1,X_2,\ldots,X_N) that satisfies all the following conditions, and if it exists, find one.
- -10^8\le X_i\le 10^8 (1\le i\le N)
- \displaystyle \sum_{i=1}^N A_iX_i > 0
- \displaystyle \sum_{i=1}^N B_iX_i < 0
You are given T test cases, so find the answer for each.
Constraints
- 1\le T\le 2\times 10^5
- 1\le N\le 2\times 10^5
- 1\le A_i,B_i\le 10^5
- The sum of N over all test cases is at most 2\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
Output
Output your solutions for the test cases in order, separated by newlines.
For each test case, if there is no X that satisfies all conditions, output No.
Otherwise, output an X that satisfies all conditions in the following format:
Yes X_1 X_2 \ldots X_N
If there are multiple X that satisfy the conditions, you may output any of them.
Sample Input 1
3 3 3 1 4 1 5 1 3 4 4 4 7 7 7 4 20 25 6 15 31 41 59 26
Sample Output 1
Yes 4 -5 1 No Yes 45 -10 -40 11
For the first test case, if we set X=(4,-5,1), then
- \displaystyle \sum_{i=1}^3 A_iX_i=3\times 4+1\times (-5)+4\times 1=11>0
- \displaystyle \sum_{i=1}^3 B_iX_i=1\times 4+5\times (-5)+1\times 1=-20<0
which satisfies the conditions. Other examples that satisfy the conditions include X=(3,-3,1) and X=(27,-40,22).