結果
問題 | No.1884 Sequence |
ユーザー |
|
提出日時 | 2022-03-25 22:38:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,681 bytes |
コンパイル時間 | 4,135 ms |
コンパイル使用メモリ | 241,324 KB |
実行使用メモリ | 17,792 KB |
最終ジャッジ日時 | 2024-10-14 06:36:19 |
合計ジャッジ時間 | 12,193 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 17 WA * 23 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#define rep(i,a,b) for(int i=a;i<b;i++)#define rrep(i,b) for(int i=b-1;i>=0;i--)#define rbit(i,a) for(int i=0;i<(1<<a);i++)#define all(x) (x).begin(),(x).end()template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }typedef long long ll;typedef long double lld;using namespace std;using namespace atcoder;using mint=static_modint<1000000007>;const ll mod=998244353;//const ll mod=1e9+7;int dx[4]={1,0,-1,0};int dy[4]={0,1,0,-1};const string zton="0123456789";const string atoz="abcdefghijklmnopqrstuvwxyz";ll gcd(ll a,ll b){ll r;r=a%b;if(r==0){return b;}else{return gcd(b,r);}}typedef pair<ll,int> P;int main(void){int N;cin >> N;ll A[N];int zero=0;map<ll,int> s;rep(i,0,N){cin >> A[i];if(A[i]==0)zero++;s[A[i]]=s[A[i]]+1;}for(auto p:s){if(p.second>=2){if(p.first==0)continue;if(s.size()==1){cout << "Yes" << endl;return 0;}if(s.size()==2){if(s.count(0)){cout << "Yes" << endl;}else{cout << "No" << endl;}return 0;}cout << "No" << endl;return 0;}}sort(A,A+N);ll d=-1;ll sum=0;ll cnt=0;rep(i,0,N-1){if(A[i]!=0&&A[i]!=A[i+1]){if(d==-1){d=A[i+1]-A[i];sum+=(A[i+1]-A[i]);cnt++;}else{ll d=gcd(d,A[i+1]-A[i]);sum+=(A[i+1]-A[i]);cnt++;}}}if(d==-1){cout << "Yes" << endl;return 0;}queue<ll> que;for(ll i=1;i*i<=d;i++){if(d%i==0){que.push(i);que.push(d/i);}}return 0;string ans="No";while(!que.empty()){ll j=que.front();que.pop();ll ex=-1;bool f=true;rep(i,0,N){if(A[i]==0)continue;if(ex==-1)ex=A[i]%j;if(ex!=A[i]%j){f=false;break;}}if(f){ll sum2=sum;sum2-=(cnt*j);sum2/=j;if(sum2<=zero){cout << "Yes" << endl;return 0;}}}cout << ans << endl;}