#428567 (C++14) No.983 Convolution

提出ソース

結果

問題	No.983 Convolution
ユーザー	NyaanNyaan
提出日時	2020-02-11 16:02:21
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	62 ms / 2,000 ms
コード長	4,581 bytes
コンパイル時間	1,743 ms
コンパイル使用メモリ	173,132 KB
実行使用メモリ	12,304 KB
最終ジャッジ日時	2024-04-08 15:30:24
合計ジャッジ時間	3,952 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	36 ms 7,936 KB
testcase_04	AC	34 ms 7,808 KB
testcase_05	AC	31 ms 7,808 KB
testcase_06	AC	55 ms 12,096 KB
testcase_07	AC	53 ms 12,096 KB
testcase_08	AC	9 ms 6,676 KB
testcase_09	AC	15 ms 6,676 KB
testcase_10	AC	6 ms 6,676 KB
testcase_11	AC	10 ms 6,676 KB
testcase_12	AC	54 ms 12,304 KB
testcase_13	AC	16 ms 6,676 KB
testcase_14	AC	17 ms 6,676 KB
testcase_15	AC	33 ms 7,936 KB
testcase_16	AC	29 ms 7,808 KB
testcase_17	AC	52 ms 12,184 KB
testcase_18	AC	9 ms 6,676 KB
testcase_19	AC	29 ms 7,808 KB
testcase_20	AC	55 ms 12,288 KB
testcase_21	AC	36 ms 7,936 KB
testcase_22	AC	9 ms 6,676 KB
testcase_23	AC	27 ms 7,936 KB
testcase_24	AC	7 ms 6,676 KB
testcase_25	AC	7 ms 6,676 KB
testcase_26	AC	24 ms 7,808 KB
testcase_27	AC	14 ms 6,676 KB
testcase_28	AC	32 ms 7,808 KB
testcase_29	AC	62 ms 12,216 KB
testcase_30	AC	33 ms 7,808 KB
testcase_31	AC	17 ms 6,676 KB
testcase_32	AC	34 ms 7,808 KB
testcase_33	AC	2 ms 6,676 KB
testcase_34	AC	2 ms 6,676 KB
testcase_35	AC	2 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define rep(i,N) for(long long i = 0; i < (long long)(N); i++)
#define repr(i,N) for(long long i = (long long)(N) - 1; i >= 0; i--)
#define rep1(i,N) for(long long i = 1; i <= (long long)(N) ; i++)
#define repr1(i,N) for(long long i = (N) ; (long long)(i) > 0 ; i--)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
using namespace std; void solve();
using ll = long long; template<class T = ll> using V = vector<T>;
using vi = V<int>; using vl = V<>; using vvi = V< V<int> >;
constexpr int inf = 1001001001; constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
  #include "NyaanDebug.h"
  #define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
  #define trca(v,N) do { cerr << #v << " = "; array_out(v , N);cout << endl;} while(0)
#else
  #define trc(...)
  #define trca(...)
  int main(){solve();}
#endif

#define inc(...) char __VA_ARGS__; in(__VA_ARGS__)
#define in2(N,s,t) rep(i,N){in(s[i] , t[i]);}
#define in3(N,s,t,u) rep(i,N){in(s[i] , t[i] , u[i]);}
using vd = V<double>; using vs = V<string>; using vvl = V< V<> >;
template<typename T>using heap = priority_queue< T , V<T> , greater<T> >;

using P = pair<int,int>; using vp = V<P>;
constexpr int MOD = /** 1000000007; //*/ 998244353;
//////////////////

template <typename T>
void fwt(vector<T>& f) {
    int n = f.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j] += f[j | i];
            }
        }
    }
}
template <typename T>
void ifwt(vector<T>& f) {
    int n = f.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j] -= f[j | i];
            }
        }
    }
}

__int128_t gcd(__int128_t x, __int128_t y){
  __int128_t z;
  if(x > y) swap(x,y);
  while(x){
    x = y % (z = x); y = z;
  }    
  return y;
}

std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}

__int128 parse(string &s) {
  __int128 ret = 0;
  for (int i = 0; i < (int)s.length(); i++)
    if ('0' <= s[i] && s[i] <= '9')
      ret = 10 * ret + s[i] - '0';
  return ret;
}

void solve(){
  ini(N);
  vi a(N); in(a);
  
  int M = 1; while(M < N) M *= 2;

  #define inf 1000000000000LL
  vector<__int128_t> b(M , 0) , f(M , 0);
  rep(i , N){
    if(a[i] != -1) b[i] = a[i] , f[i] = 1;
    else b[i] = 0 , f[i] = inf;
  }
  
  fwt(b); each(x , b) x *= x; ifwt(b);
  fwt(f); each(x , f) x *= x; ifwt(f);
  //rep(i , N) trc(i , (ll)(b[i]) , (ll)(f[i]));
  __int128_t ans = 0;
  rep(i , N){
    ans = gcd(ans , b[i]);
  }
  ans = (ans == 0) ? -1 : ans;
  cout << ans << "\n";
}

yukicoder

結果

テストケース

ソースコード