J.Eat, Sleep, Repeat

J. Eat, Sleep, Repeat
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

FuuFuu the Panda, together with Pico and Kotsuki, lives in the KFP apartment. As a rare species, FuuFuu is well-treated. Therefore, his daily activities are only eating and sleeping.

One afternoon, Kotsuki is still working outside, and FuuFuu has finished his lunch and intends to go to sleep. But Pico feels too bored to play alone every day and wants to play a game with FuuFuu for a while. Although not very reluctant, FuuFuu agrees.

Pico picks n integers a1,a2,…an, and sets k constraints, the i-th of which is limitxi=yi, indicating that the maximum number of occurrences of xi is yi. Then Pico and FuuFuu take turns playing the game, where each player can choose a positive integer among a1,a2,…an for each turn and reduce it by 1. A player will lose the game if he cannot perform any action on his turn, where there are two cases:

No matter which of a1,a2,…an is chosen, there exists an integer x whose number of occurrences will be strictly greater than limitx.
a1=a2=⋯=an=0.
Even though FuuFuu is sleepy, he does not want to lose the game. Please tell him who will win if Pico goes first and both of them play optimally.

Input
The first line contains an integer T (1≤T≤105), indicating the number of test cases.

The first line of each test case contains two integers n and k (1≤n≤105, 0≤k≤105), indicating the number of integers and constraints.

The second line contains n integers a1,a2,…an (0≤ai≤109), indicating the initial integers. It is guaranteed that the initial number of occurrences of each integer does not exceed the limit.

The i-th of the following k lines contains two integers xi and yi (0≤xi≤109, 0≤yi≤n), indicating that limitxi=yi. It is guaranteed that x1,x2,…xk are all distinct.

It’s guaranteed that ∑n≤105 and ∑k≤105 over all test cases.

Output
For each test case, output the name of the winner in a single line, which is either Pico or FuuFuu.

Example
inputCopy
5
2 0
1 2
2 1
1 2
0 1
3 2
3 3 4
0 2
1 1
3 2
2 3 3
1 2
0 1
5 4
6 7 8 12 17
1 1
2 1
9 0
10 1
outputCopy
Pico
FuuFuu
Pico
FuuFuu
Pico
Note
For the first test case of the sample, since there are no constraints, the game ends only if all the integers are reduced to zero. So FuuFuu will lose the game after three turns.

For the second test case of the sample, the maximum number of occurrences of 0 is 1. Obviously, there must be two zeros after Pico’s action in the third turn, so FuuFuu will win the game.

题意：

• 给你n个数，以及m个限制，每个限制有两个数x和y，表示数x最多只能同时出现y个。
• 每次两个玩家会选一个数-1，最先做不出操作的就输了。
• Pico 先手并且两人都发挥最佳，求谁会赢？

思路：

• 如果x最多出现次数为0，说明比他大的数都只能停在x+1上了，不能更小。然后剩下的数则可以贪心的能删多小删多小。
• 既然最终结果定了，不难发现其实操作次数与策略无关。
  所以直接模拟，用map统计每个数的限制，将数组排序，从前往后扫，每个数可以减小的值 = 第一个小于等于它的无限制 或 个数未达到上限的值，用一个小根堆去维护所有可行位置。
• 最后只需要统计一下所有可以进行的操作数，是奇数还是偶数即可得到答案。

#include
using namespace std;
typedef long long LL;
const int maxn = 2e6+10;
int a[maxn];
int main(){int T;  cin>>T;while(T--){int n, k;  cin>>n>>k;for(int i = 1; i <= n; i++)cin>>a[i];mapmp;priority_queue, greater>q;q.push(0);while(k--){int x, y;  cin>>x>>y;if(y==0)q.push(x+1); //不能出现xelse mp[x] = y;}sort(a+1,a+n+1);int res = 0, t = 0;for(int i = 1; i <= n; i++){while(q.size() && q.top()<=a[i]){//第1个<=a[i]的无限制可以出现的数t = q.top();  q.pop();}res ^= (a[i]-t)&1;       //统计和的奇偶性mp[t]--;                 //剩余出现个数--if(mp[t]==0)q.push(t+1); //如果x限制数为0，则比他大的数都只能停在x+1上了。}if(res)cout<<"Pico\n";else cout<<"FuuFuu\n";}return 0;
}

C.Grass

C. Grass
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

Charles the Rabbit likes eating grass. As the saying goes, rabbits do not eat the grass by their burrows. Therefore, Charles has to go outside his burrow every day to look for grass to eat.

One day, Charles comes to a two-dimensional plane with many distinct points. He can choose a point A and another four points B,C,D,E to connect with A to form four segments. We consider these four segments as a clump of grass if they meet the following condition:

Any two of the four segments have only a single point of intersection A between them.
For example, in the picture below, (1) is a clump of grass, but (2) is not one as the intersection of segments AC and AE is not only a single point A.

Given n points on a plane, Charles wants to know whether there exists a clump of grass. If so, help him find a certain one.

Input
The first line contains an integer T (1≤T≤120), indicating the number of test cases.

The first line of each test case contains an integer n (1≤n≤25000), indicating the number of points.

Each of the following n lines contains two integers x,y (−107≤x,y≤107), indicating that the coordinates of the point are (x,y). It is guaranteed that all points are distinct.

It is guaranteed that ∑n≤105 over all test cases.

Output
For each test case, if there does not exist a clump of grass, output NO in a single line.

Otherwise, output YES in the first line. Then output two integers separated by a space in the second line, indicating the coordinates of point A. Then output two integers separated by a space in each of the third to sixth lines, indicating the coordinates of the other four points B,C,D,E.

If there is more than one clump of grass, output any.

Example
inputCopy
3
5
0 0
1 1
1 -1
-1 1
-1 -1
3
1 1
4 5
1 4
5
1 0
2 0
3 0
4 0
5 0
outputCopy
YES
0 0
1 1
1 -1
-1 1
-1 -1
NO
NO

题意：

• T组数据（120），每次给出二维平面的n个点（2e4），求是否能找出5个点满足点 A 和另外四个点 B、C、D、E 与 A 连接形成四个线段，输出这五个点（按照ABCDE的顺序）。

思路：

• 不难发现结论：只要BCDE四个点不是都和A共线的，就能有结果，哪怕BCDE四个点都是共线。
• 先固定4个点，O（n）寻找一个和他们不共线的点，如果找不到则必然没有可行解，如果找到，则判断一下哪一个点是中心点即可。
• 除非输入的n个点都共线（此时自然无解），否则固定4个点，必然可以找到一个点与之不是共线的情况。

#include
using namespace std;
typedef long long LL;
typedef pair PII;
const LL maxn = 2e6+10;
struct node{LL x, y; }a[maxn];LL check(LL x){setse;for(LL i = 1; i <= 4; i++){LL dx = a[i].x-a[x].x, dy = a[i].y-a[x].y;LL dd = __gcd(dx, dy);dx /= dd;  dy /= dd;se.insert({dx, dy});}return se.size()>1;  //只要有不是五点共线就行
}
LL find(){for(LL i = 1; i <= 5; i++){setse;for(LL j = 1; j <= 5; j++){if(i==j)continue;LL dx = a[i].x-a[j].x, dy = a[i].y-a[j].y;LL dd = abs(__gcd(dx, dy));dx /= dd;  dy /= dd;se.insert({dx, dy});}if(se.size()==4)return i;}
}int main(){LL T;  cin>>T;while(T--){LL n;  cin>>n;for(LL i = 1; i <= n; i++)cin>>a[i].x>>a[i].y;LL ok = 0;for(LL i = 5; i <= n; i++){if(check(i)){swap(a[i], a[5]);LL x = find();cout<<"YES\n";cout<if(i!=x)cout<

#include
using namespace std;int w[19], f[1<<19], vis[1<<19];
vector >v[19];     //格子i作为跳板时，合法的跳跃前后格子
void add(int mid, int a, int b){ //跳板格子，以及跳跃前后的两个格子v[mid].push_back({a,b});v[mid].push_back({b,a});
}int dfs(int now){if(vis[now])return f[now];//op1, remove ifor(int i = 0; i < 19; i++){if(!(now>>i&1))continue; f[now] = max(f[now], dfs(now-(1<if(!(now>>i&1))continue;for(auto p : v[i]){int x = p.first, y = p.second;if(!(now>>x&1) || (now>>y&1))continue;//x to y (by i), +w[i]f[now] = max(f[now], dfs(now-(1<//输入和建图memset(f, 0xc0, sizeof(f));f[0] = 0;  vis[0] = 1;add(1, 0, 2);add(3, 0, 7);add(4, 0, 9), add(4, 1, 8), add(4, 3, 5);add(5, 1, 10), add(5, 2, 9), add(5, 4, 6);add(6, 2, 11);add(8, 3, 13), add(8, 4, 12), add(8, 7, 9);add(9, 4, 14), add(9, 5, 13), add(9, 8, 10);add(10, 5, 15), add(10, 6, 14), add(10, 9, 11);add(12, 7, 16);add(13, 8, 17), add(13, 9, 16), add(13, 12, 14);add(14, 9, 18), add(14, 10, 17), add(14, 13, 15);add(15, 11, 18);add(17, 16, 18);//solveios::sync_with_stdio(0), cin.tie(0), cout.tie(0);for(int i = 0; i < 19; i++)cin>>w[i];int T;  cin>>T;while(T--){string s, t;for(int i = 0; i < 5; i++)cin>>t, s += t;int st = 0;for(int i = 0; i < 19; i++){if(s[i]=='#')st += 1<

#include
using namespace std;
typedef long long LL;
const LL maxn = 5e5+10;
LL n, k, a[maxn], b[maxn], c[maxn];LL check(LL mid){priority_queue, less>q;for(LL i = 1; i <= n; i++)q.push(a[i]*mid);for(LL i = 1; i <= k; i++)c[i] = b[i];LL cur = k, spd = (1<<(cur-1));while(q.size()){LL need = q.top();  q.pop();LL cnt = max(1LL, min(c[cur], need / spd));c[cur] -= cnt;need -= cnt*spd;if(need > 0)q.push(need);if(c[cur]==0){cur--;spd = (1 << (cur-1));if(cur == 0)return q.size()==0;}}return 1;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);LL T;  cin>>T;while(T--){cin>>n>>k;LL s1 = 0, s2 = 0;for(LL i = 1; i <= n; i++)cin>>a[i], s1 += a[i];for(LL i = 1; i <= k; i++)cin>>b[i], s2 += b[i]*(1<<(i-1));LL l = 0, r = s2/s1+100;while(l < r){LL mid = l+(r-l+1)/2; //向上取整, 不然3,4死循环if(check(mid))l = mid;else r = mid-1;}cout<