結果
問題 |
No.983 Convolution
|
ユーザー |
|
提出日時 | 2020-02-11 14:29:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,004 bytes |
コンパイル時間 | 1,618 ms |
コンパイル使用メモリ | 183,024 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-01 07:40:15 |
合計ジャッジ時間 | 3,395 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 WA * 24 |
ソースコード
#include<bits/stdc++.h> #define rep(i, n) for(int i=0;i<(n);++i) #define per(i, n) for(int i=(n)-1;i>=0;--i) #define repa(i, n) for(int i=1;i<(n);++i) #define foreach(i, n) for(auto &i:(n)) #define pii pair<int, int> #define pll pair<long long, long long> #define all(x) (x).begin(), (x).end() #define bit(x) (1ll << (x)) using ll = long long; //const ll MOD = (ll)1e9+7; const ll MOD = 998244353; const int INF = (ll)1e9+7; const ll INFLL = (ll)1e18; using namespace std; template<class t> using vvector = vector<vector<t>>; template<class t> using vvvector = vector<vector<vector<t>>>; template<class t> using priority_queuer = priority_queue<t, vector<t>, greater<t>>; template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;} template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;} #ifdef DEBUG #define OUTPUT(x) (output(x), output("\n")) #else #define OUTPUT(x) (void)0 #endif ll modpow(ll x, ll b){ ll res = 1; while(b){ if(b&1)res = res * x % MOD; x = x * x % MOD; b>>=1; } return res; } ll modinv(ll x){ return modpow(x, MOD-2); } bool was_output = false; template<class t> void output(t a){ if(was_output)cout << " "; cout << a; was_output = true; } void outendl(){ was_output = false; cout << endl; } map<ll, ll> prime_melt(ll x){ map<ll, ll> res; for(int i=2;i*i<=x;++i){ int cnt=0; while(x%i==0){ ++cnt; x/=i; } if(cnt){ res[i] = cnt; } } if(x!=1)res[x] = 1; return res; } ll norpow(ll x, ll b){ ll res = 1; while(b){ if(b&1)res = res * x; x = x * x; b>>=1; } return res; } ll gcd(ll a, ll b){ while(b){ a%=b; swap(a, b); } return a; } ll pop_count(ll x){ ll res = 0; while(x){ if(x&1)++res; x>>=1; } return res; } int main(){ int n; cin >> n; vector<ll> line(n); foreach(i, line){ cin >> i; } int cnt = [](vector<ll> line){ int res = 0; foreach(i, line){ if(i!=-1)++res; } return res; }(line); if(cnt==0){ cout << -1 << endl; return 0; } if(cnt>=100){ ll ans = line[0]; foreach(i, line){ ans = gcd(i, ans); } cout << ans << endl; return 0; } vector<pll> nline; rep(i, n){ if(line[i]==-1)continue; nline.emplace_back(line[i], i); } vector<ll> ans(n, 0); foreach(i, nline){ foreach(j, nline){ ans[i.second&j.second] += i.first * j.first; } } [](vector<ll> line){ ll ans = -1; foreach(i, line){ if(i==0)continue; if(ans==-1){ ans = i; }else{ ans = gcd(ans, i); } } cout << ans << endl; }(ans); return 0; }