#748374 (C++17) No.1884 Sequence

• 問題: No.1884 Sequence
• ユーザー: 沙耶花
• 提出日時: 2022-03-25 21:32:43
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 279 ms / 2,000 ms
• コード長: 877 bytes
• コンパイル時間: 4,181 ms
• コンパイル使用メモリ: 263,232 KB
• 実行使用メモリ: 29,952 KB
• 最終ジャッジ日時: 2024-04-22 06:09:29
• 合計ジャッジ時間: 10,822 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	279 ms; 29,824 KB
testcase_11	AC	279 ms; 29,952 KB
testcase_12	AC	85 ms; 14,720 KB
testcase_13	AC	91 ms; 15,616 KB
testcase_14	AC	67 ms; 14,080 KB
testcase_15	AC	170 ms; 17,408 KB
testcase_16	AC	244 ms; 17,280 KB
testcase_17	AC	130 ms; 17,408 KB
testcase_18	AC	167 ms; 17,408 KB
testcase_19	AC	134 ms; 15,360 KB
testcase_20	AC	141 ms; 21,888 KB
testcase_21	AC	144 ms; 20,352 KB
testcase_22	AC	163 ms; 22,912 KB
testcase_23	AC	246 ms; 17,280 KB
testcase_24	AC	245 ms; 17,280 KB
testcase_25	AC	236 ms; 17,408 KB
testcase_26	AC	241 ms; 17,408 KB
testcase_27	AC	33 ms; 5,376 KB
testcase_28	AC	32 ms; 5,376 KB
testcase_29	AC	37 ms; 5,376 KB
testcase_30	AC	103 ms; 17,408 KB
testcase_31	AC	135 ms; 14,976 KB
testcase_32	AC	225 ms; 17,280 KB
testcase_33	AC	119 ms; 5,376 KB
testcase_34	AC	113 ms; 5,376 KB
testcase_35	AC	40 ms; 5,376 KB
testcase_36	AC	88 ms; 5,376 KB
testcase_37	AC	183 ms; 17,280 KB
testcase_38	AC	106 ms; 5,376 KB
testcase_39	AC	54 ms; 5,376 KB
testcase_40	AC	58 ms; 5,376 KB
testcase_41	AC	201 ms; 17,280 KB
testcase_42	AC	219 ms; 17,280 KB

ソースコード

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define Inf 1000000001


int main(){
	
	int n;
	cin>>n;
	
	vector<long long> a(n);
	rep(i,n){
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	if(a.back()==0 || a[n-2]==0){
		cout<<"Yes"<<endl;
		return 0;
	}
	
	
	long long g = 0;
	rep(i,n){
		if(a[i]==0)continue;
		g = gcd(g,a.back()-a[i]);
	}
	map<long long,long long> mp;
	rep(i,a.size())mp[a[i]]++;
	
	long long m = a.back();
	long long M = a.back();

	rep(i,a.size()){
		if(a[i]!=0)m = min(a[i],m);
	}
	
	rep(i,n){
		if(mp[m]>0){
			mp[m]--;
		}
		else{
			mp[0]--;
		}
		m += g;
		if(m>100000000000000000)m = 100000000000000000;
	}
	for(auto x:mp){
		if(x.second!=0){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	
	return 0;
}