結果
問題 | No.2821 A[i] ← 2A[j] - A[i] |
ユーザー |
|
提出日時 | 2024-07-26 21:48:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 612 ms / 1,500 ms |
コード長 | 3,273 bytes |
コンパイル時間 | 5,467 ms |
コンパイル使用メモリ | 314,496 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-26 21:49:04 |
合計ジャッジ時間 | 11,266 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;typedef long long ll;typedef long double ld;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<ll> vl;typedef vector<vl> vvl;typedef vector<ld> vd;typedef vector<vd> vvd;typedef vector<char> vc;typedef vector<vc> vvc;typedef vector<string> vs;typedef vector<vs> vvs;typedef vector<bool> vb;typedef vector<vb> vvb;typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef modint998244353 mint; // atcodertypedef vector<mint> vm; // atcodertypedef vector<vm> vvm; // atcodertemplate<class T> using pqmax = priority_queue<T, vector<T>, less<T>>; // 昇順template<class T> using pqmin = priority_queue<T, vector<T>, greater<T>>; // 降順#define overload4(_1,_2,_3,_4,name,...) name#define REP1(n) for(ll i=0;i<n;i++)#define REP2(i,n) for(ll i=0;i<n;i++)#define REP3(i,a,b) for(ll i=a;i<b;i++)#define REP4(i,a,b,c) for(ll i=a;i<b;i+=c)// 1: 0->n-1, 2: i,0->n-1, 3: i,a->b-1, 4: i,a->b-1,c#define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)#define RREP1(n) for(ll i=n;i>0;i--)#define RREP2(i,n) for(ll i=n;i>0;i--)#define RREP3(i,a,b) for(ll i=a;i>b;i--)#define RREP4(i,a,b,c) for(ll i=a;i>b;i-=c)// 1: n->1, 2: i,n->1, 3: i,a->b+1, 4: i,a->b+1,c#define RREP(...) overload4(__VA_ARGS__, RREP4, RREP3, RREP2, RREP1)(__VA_ARGS__)#define REPA(i, a) for(auto&&i:a)#define ALL(x) x.begin(), x.end()#define SZ(x) (int)x.size()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; }template<class... T>constexpr auto min(T... a){ return min(initializer_list<common_type_t<T...>>{a...}); }template<class... T>constexpr auto max(T... a){ return max(initializer_list<common_type_t<T...>>{a...}); }template<class... T>void input(T&... a){ (cin >> ... >> a); }void print(){ cout << endl; }template<class T, class... Ts>void print(const T &a, const Ts &...b){ cout << a; (cout << ... << (cout << ' ', b)); cout << endl; }void debug(){ cerr << endl; }template<class T, class... Ts>void debug(const T &a, const Ts &...b){ cerr << a; (cerr << ... << (cerr << ' ', b)); cerr << endl; }template <class T> vector<T> make_vector(const size_t &a, const T &b) { return vector<T>(a, b); }template <class... Ts> auto make_vector(const size_t &a, const Ts &...b) { return vector<decltype(make_vector(b...))>(a, make_vector(b...)); }constexpr int MOD = 998244353;constexpr int inf = 1001001001;constexpr ll INF = 1001001001001001001;int main(){// cin.tie(0);// ios::sync_with_stdio(0);// cout << fixed << setprecision(20);int N;cin >> N;vl A(N);REP(i, N) cin >> A[i];set<ll> st;st.emplace(-INF);st.emplace(INF);ll g = 0;REP(i, N){if (st.count(A[i]) == 0){auto p = st.upper_bound(A[i]);ll right = *p;p--;ll left = *p;if (left != -INF){g = gcd(g, A[i] - left);}if (right != INF){g = gcd(g, right - A[i]);}}print(g);st.emplace(A[i]);}return 0;}