結果
問題 | No.1884 Sequence |
ユーザー |
![]() |
提出日時 | 2022-06-04 15:44:37 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,231 bytes |
コンパイル時間 | 11,608 ms |
コンパイル使用メモリ | 281,540 KB |
最終ジャッジ日時 | 2025-01-29 18:08:13 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 40 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> using namespace std; using ll = long long; const int INF = 1e9; const ll inf = 1LL<<62; void solve() { ll n; cin >> n; auto gcd = [](auto&& gcd, ll x, ll y) -> ll { if (x == 0 || y == 0) return x+y; if (x%y) return gcd(gcd, y, x%y); return y; }; ll g = 0; int cnt = 0; vector<ll> a; for (int i=0; i<n; i++) { ll A; cin >> A; if (A == 0) cnt++; else a.emplace_back(A); } if (a.size() <= 2) { cout << "YES" << '\n'; return; } sort(a.begin(), a.end()); for (int i=1; i<a.size(); i++) { if (a[i] == a[i-1]) { for (int j=1; j<a.size(); j++) { if (a[0] != a[j]) { cout << "NO" << '\n'; return; } } cout << "YES" << '\n'; return; } g = gcd(gcd, g, a[i] - a[i-1]); } assert(g != 0); for (int i=1; i<a.size(); i++) { ll p = (a[i] - a[i-1])/g; p--; if (p > cnt) { cout << "NO" << '\n'; return; } cnt -= p; } cout << "YES" << '\n'; } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); // int t; cin >> t; /*while (t--)*/ solve(); }