結果
問題 | No.1884 Sequence |
ユーザー |
|
提出日時 | 2022-03-25 23:00:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 3,242 bytes |
コンパイル時間 | 2,697 ms |
コンパイル使用メモリ | 293,348 KB |
最終ジャッジ日時 | 2025-01-28 12:29:47 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>#include <boost/multi_array.hpp>#include <boost/optional.hpp>#include <boost/range/irange.hpp>#include <boost/range/algorithm.hpp>#include <boost/range/adaptors.hpp>using namespace std;namespace adaptor = boost::adaptors;using ll = long long;using ull = unsigned long long;using ld = long double;using vi = vector<int>;using vvi = vector<vi>;using vvvi = vector<vvi>;using vl = vector<long>;using vvl = vector<vl>;using pii = pair<int, int>;using pll = pair<long, long>;using vpii = vector<pii>;using vpll = vector<pll>;using vstr = vector<string>;constexpr ll INF_LL=1LL<<60;constexpr int INF_I=1LL<<30;#define rep(i,n) for(int i=0; i<((int)(n)); i++)#define reps(i,n) for(int i=1; i<=((int)(n)); i++)#define rrep(i,n) for(int i=((int)(n)); i>0; i--)#define rreps(i,n) for(int i=((int)(n)-1); i>=0; i--)#define vector_cin(x) for(auto &n : (x)) cin >> n#define ALL(x) (x).begin(), (x).end()#define YesNo(x) ((x) ? "Yes" : "No")#define pb emplace_backtemplate <class BidirectionalIterator, class Compare>bool next_combination(BidirectionalIterator first, BidirectionalIterator last,Compare comp, size_t r){BidirectionalIterator subset = first + r;if (first == last || first == subset || last == subset) {return false;}BidirectionalIterator src = subset;while (first != src) {src--;if (comp(*src, *(last - 1))) {BidirectionalIterator dst = subset;while (*src >= *dst) {dst++;}std::iter_swap(src, dst);std::rotate(src + 1, dst + 1, last);std::rotate(subset, subset + (last - dst) - 1, last);return true;}}rotate(first, subset, last);return false;}template <class BidirectionalIterator>bool next_combination(BidirectionalIterator first, BidirectionalIterator last,size_t r){using value_type =typename std::iterator_traits<BidirectionalIterator>::value_type;return next_combination(first, last, std::less<value_type>(), r);}template <typename T>bool chmax(T &a, const T& b) {if (a < b){a = b;return true;}return false;}template <typename T>bool chmin(T &a, const T& b) {if (a > b){a = b;return true;}return false;}ll ceilint(ll x, ll y) { // x/y の 切り上げreturn (x + y - 1) / y;}void Main();int main() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << std::fixed << std::setprecision(15);Main();return 0;}//-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-void Main() {ll N;cin >> N;vector<ll> A(N);vector_cin(A);sort(ALL(A));vector<ll> diff;ll can_use = 0;rep(i, N - 1)if (A[i] == 0)can_use++;elsediff.pb(A[i + 1] - A[i]);ll num = -1;bool flag = false;rep(i, diff.size()) {if (diff[i] == 0) {flag = true;continue;}if (num == -1)num = diff[i];num = gcd(num, diff[i]);}bool ans = true;if (flag) {rep(i, N - 1) {if (A[i] == 0)continue;if (A[i + 1] != A[i])ans = false;}cout << YesNo(ans) << endl;return;}rep(i, diff.size())can_use -= diff[i] / num - 1;if (can_use < 0)ans = false;if (num == -1)ans = true;cout << YesNo(ans) << endl;}