求调Div2 D
  • 板块学术版
  • 楼主02Ljh
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/9/11 00:39
  • 上次更新2023/11/2 21:30:48
查看原帖
求调Div2 D
578004
02Ljh楼主2023/9/11 00:39
// Problem: D1. Candy Party (Easy Version)
// Contest: Codeforces - Codeforces Round 896 (Div. 2)
// URL: https://codeforces.com/contest/1869/problem/D1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
#define ull unsigned long long
#define ll long long
#define MAXN 200019
#define WA cerr<<"CCF\n";
#define eps 1e-5
#define none -1145141919
#define pii pair<int,int>
#define Y cout<<"Yes\n"
#define N cout<<"No\n"
#define H cout<<"\n"
const int MOD=1e9+7;
int a[MAXN]; int n;
int lowbit(int x) { return x&-x; }
vector<int> op,ip;
int hjl(int x)
{
	int lg=log2(x);
	while(x)
	{
		if(!(x&1)) return -1; 
		x>>=1;
	}
	return lg;
}
 main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _; cin>>_;
	for(int __=1;__<=_;__++)
	{
		ip.clear();
		op.clear();
		int sum=0;
		int maxn=0;
		cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; sum+=a[i]; maxn=max(maxn,a[i]); }
		if(sum%n!=0) { N; continue; }
		sum/=n;
		//cout<<sum<<"\n";
		for(int i=1;i<=n;i++)
		{
			if(sum==a[i]) continue;
			int t=abs(sum-a[i]);
			int len=log2(lowbit(t));
			int ig=(1<<(len+1));
			t=t>>len;
			//cout<<__<<" "<<len<<" "<<t<<"\n";
			int yu=hjl(t);
			if(yu==-1) { N; n=-1; break; }
			int og=(1<<(len+yu));
			if(a[i]>sum) swap(ig,og);
			ip.push_back(ig); op.push_back(og); 
		}
		if(n==-1) continue;
		sort(ip.begin(),ip.end());
		sort(op.begin(),op.end());
		for(int i=0;i<ip.size();i++)
		{
			if(op[i]!=ip[i]||(op[i]>maxn*2)||(ip[i]>maxn*2)) { N; n=-1; break; }
			//cout<<ip[i]<<" "<<op[i]<<"\n";
		}
		if(n==-1) continue;
		Y;
	} 
    return 0;
}
/*
Need check before submit

1.INF=1e9 check if the val>=1e9 and only 0x3f3f3f3f and 0 can be memset!!!
2.Don't using getchar() unless is NESSASARY!!!
3.Enough size for the array!!!
4.Notice double's precision
5.CHECK UR LL OR ULL!!!
6.READ THE PROBLEM AGAIN AND AGAIN!!!

*/

WA 6

2023/9/11 00:39
加载中...