fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define loopf(i,a,b) for(ll i=a;i<b;i++)
  5. #define loopb(i,a,b) for(ll i=a;i>b;i--)
  6. #define pb push_back
  7. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
  8. #define ff first
  9. #define ss second
  10. #define vc vector
  11. #define pii pair<int,int>
  12. #define pll pair<ll,ll>
  13. //General defs
  14. #define umap unordered_map
  15. #define uset unordered_set
  16. //Along with data types
  17. #define mapii map<int,int>
  18. #define mapll map<ll,ll>
  19. #define seti set<int>
  20. #define setll set<ll>
  21. #define umapii unordered_map<int,int>
  22. #define useti unordered_set<int>
  23. #define umapll unordered_map<ll,ll>
  24. #define usetll unordered_set<ll>
  25. #define all(x) x.begin(),x.end()
  26. const ll M=1e9+7;
  27.  
  28. //send the value and the line number
  29. #define debug(i,line) cout << #i <<" = " << i<<" on the line "<<line<<endl;
  30.  
  31.  
  32. void print(ll arr[],ll n){
  33. 	loopf(i,0,n)
  34. 	cout<<arr[i]<<" ";
  35. 	cout<<endl;
  36. }
  37. void print(int arr[],int n){
  38. 	loopf(i,0,n)
  39. 	cout<<arr[i]<<" ";
  40. 	cout<<endl;
  41. }
  42. void print(int arr[],ll n){
  43. 	loopf(i,0,n)
  44. 	cout<<arr[i]<<" ";
  45. 	cout<<endl;
  46. }
  47. void print(vc<ll> arr,ll n){
  48. 	loopf(i,0,n)
  49. 	cout<<arr[i]<<" ";
  50. 	cout<<endl;
  51. }
  52.  
  53.  
  54. //send a vector of long long along with the number below which you want to store
  55. void sieve(vc<ll> &P,ll n)
  56. {
  57.     bool prime[n + 1];
  58.     memset(prime, true, sizeof(prime));
  59.     for (ll p = 2; p * p <= n; p++)
  60.     {
  61.  
  62.         if (prime[p] == true)
  63.         {
  64.  
  65.             for (int i = p * p; i <= n; i += p)
  66.                 prime[i] = false;
  67.         }
  68. 	}
  69.     for (ll p = 2; p <= n; p++)
  70.         if (prime[p])
  71.             P.pb(p);
  72. }
  73.  
  74.  
  75. //Check if a number is prime
  76. bool check_prime(int n) {
  77.     if (n <= 1)  return false;
  78.     if (n <= 3)  return true;
  79.     if (n%2 == 0 || n%3 == 0) return false;
  80.     for (ll i=5; i*i<=n; i=i+6)
  81.         if (n%i == 0 || n%(i+2) == 0)
  82.            return false;
  83.     return true;
  84. }
  85. bool check_prime(ll n) {
  86.     if (n <= 1)  return false;
  87.     if (n <= 3)  return true;
  88.     if (n%2 == 0 || n%3 == 0) return false;
  89.     for (ll i=5; i*i<=n; i=i+6)
  90.         if (n%i == 0 || n%(i+2) == 0)
  91.            return false;
  92.     return true;
  93. }
  94.  
  95. //GCD function
  96. ll gcd(ll a,ll b){
  97. 	ll ans=__gcd(a,b);
  98. 	return ans;
  99. }
  100. ll gcd(int a,int b){
  101. 	ll ans=__gcd(a,b);
  102. 	return ans;
  103. }
  104.  
  105. //LCM
  106. ll lcm(ll a,ll b){
  107. 	ll ans=a*b/gcd(a,b);
  108. 	return ans;
  109. }
  110. ll lcm(int a,int b){
  111. 	ll ans=a*b/gcd(a,b);
  112. 	return ans;
  113. }
  114.  
  115.  
  116.  
  117. bool check_palindrome(string s)
  118. {
  119. 	ll n=s.length();
  120.  
  121. 	for(int i=0,j=n-1 ; i<j ; i++,j-- )
  122. 	if(s[i]!=s[j]) return false;
  123.  
  124. 	return true;
  125. }
  126.  
  127. ll power(ll a,ll n)
  128. {
  129. 	ll res=1,mod=M;
  130. 	while(n)
  131. 	{
  132. 		if(n%2)
  133. 		res=(res*a)%mod;
  134.  
  135. 		a=(a*a)%mod;
  136. 		n=n/2;
  137. 	}
  138.  
  139. 	return res;
  140. }
  141.  
  142.  
  143.  
  144. vc<ll> fact;
  145. void calculate_factorials(ll n)
  146. {
  147. 	fact.resize(n+1,1);
  148. 	ll ans=1;
  149. 	loopf(i,1,n+1)
  150. 	{
  151. 		ans= ((ans%M)*(i%M))%M;
  152. 		fact[i]=ans;
  153. 	}
  154.  
  155. }
  156.  
  157.  
  158. ll inverse(ll n)
  159. {
  160. 	return power(n,M-2);
  161. }
  162.  
  163.  
  164.  
  165. ll ncr(ll n,ll r)
  166. {
  167. 	if(r==0) return 1;
  168. 	if(r==1 || r==(n-1)) return n;
  169. 	if(r>n || r<0) return -1;
  170.  
  171. 	ll ans=((fact[n]*inverse(fact[r]))%M * (inverse(fact[n-r]))%M)%M;
  172. 	return ans;
  173. }
  174.  
  175. // ******Author- M.S.A. Tanzeel ******
  176. //***************************
  177.  
  178.  
  179. void solve()
  180. {
  181. 	ll n;
  182. 	cin>>n;
  183. 	ll x;
  184.  
  185. 	mapll m;
  186. 	loopf(i,0,2*n)
  187. 	{
  188. 		cin>>x;
  189. 		m[x]++;
  190. 	}
  191.  
  192. 	for(auto a: m)
  193. 	{
  194. 		if(a.ss&1 || a.ff&1)
  195. 		{
  196. 			cout<<"NO"<<endl;
  197. 			return;
  198. 		}
  199. 	}
  200.  
  201. 	ll arr[n];
  202.  
  203. 	ll cnt=0;
  204. 	for(auto a:m)
  205. 	arr[cnt++]=a.ff;
  206.  
  207. //	print(arr,n);
  208.  
  209. 	ll hash[n]={0};
  210.  
  211. 	if(arr[n-1]%(2*n)!=0)
  212. 	{
  213. 		cout<<"NO"<<endl;
  214. 			return;
  215. 	}
  216.  
  217. 	hash[n-1]=arr[n-1]/(2*n);
  218. 	cnt=hash[n-1];
  219. 	ll tmp=2*n-2;
  220.  
  221. 	loopb(i,n-2,-1)
  222. 	{
  223. 		arr[i]=arr[i]-2*cnt;
  224. 		if(arr[i]<=0 || arr[i]%tmp!=0)
  225. 		{
  226. 			cout<<"NO"<<endl;
  227. 			return;
  228. 		}
  229.  
  230. 		hash[i]=arr[i]/tmp;
  231. 		cnt+=hash[i];
  232. 		tmp-=2;	
  233. 	}
  234.  
  235. //	print(hash,n);
  236.  
  237. 	cout<<"YES"<<endl;
  238.  
  239.  
  240.  
  241. }
  242.  
  243. //*************************
  244. //*************************
  245.  
  246.  
  247.  
  248. int main()
  249. {
  250. 	//set this value to 1 to take test cases else 0
  251. 	bool take_test_cases=1;
  252.  
  253. 	if(take_test_cases)
  254. 	{
  255. 		int t;
  256. 		cin>>t;
  257. 		while(t--)
  258. 		solve();
  259. 	}
  260. 	else
  261. 	solve();
  262. }
  263.  
Success #stdin #stdout 0s 4828KB
comments (?)
stdin
copy 
6
2
8 12 8 12
2
7 7 9 11
2
7 11 7 11
1
1 1
4
40 56 48 40 80 56 80 48
6
240 154 210 162 174 154 186 240 174 186 162 210
stdout
copy 
YES
NO
NO
NO
NO
YES
https://ideone.com/v3h51g
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!