結果
問題 |
No.983 Convolution
|
ユーザー |
|
提出日時 | 2020-02-11 14:37:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,954 bytes |
コンパイル時間 | 1,703 ms |
コンパイル使用メモリ | 178,284 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-01 07:42:05 |
合計ジャッジ時間 | 3,391 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 WA * 26 |
ソースコード
#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; } ll gcd(ll a, ll b){ while(b){ a%=b; swap(a, b); } return a; } 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); bool is_all = [](vector<ll> line){ int n = line.size(); vector<bool> check(n, false); rep(i, n){ check[i] == line[i] == -1; } per(i, n){ if(!check[i])return false; rep(j, 31){ if(bit(j)&i){ check[bit(j)^i] = true; } } } return true; }(line); if(is_all){ cout << -1 << endl; return 0; } if(cnt<=1){ 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; }