結果

問題 No.3041 非対称じゃんけん
ユーザー erbowl
提出日時 2025-03-01 09:58:36
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 14,330 bytes
コンパイル時間 5,065 ms
コンパイル使用メモリ 435,400 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-03-01 09:59:01
合計ジャッジ時間 23,624 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 25 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

typedef long long ll;
typedef long double ld;
#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
// Union-Find
struct UnionFind {
  // core member
  vector<int> par;
  // constructor
  UnionFind() {}
  UnionFind(int n) : par(n, -1) {}
  void init(int n) { par.assign(n, -1); }
  // core methods
  int root(int x) {
    if (par[x] < 0)
      return x;
    else
      return par[x] = root(par[x]);
  }
  bool same(int x, int y) { return root(x) == root(y); }
  bool merge(int x, int y) {
    x = root(x), y = root(y);
    if (x == y) return false;
    if (par[x] > par[y]) swap(x, y);  // merge technique
    par[x] += par[y];
    par[y] = x;
    return true;
  }
  int size(int x) { return -par[root(x)]; }
  // get groups
  vector<vector<int>> groups() {
    vector<vector<int>> member(par.size());
    for (int v = 0; v < (int)par.size(); ++v) {
      member[root(v)].push_back(v);
    }
    vector<vector<int>> res;
    for (int v = 0; v < (int)par.size(); ++v) {
      if (!member[v].empty()) res.push_back(member[v]);
    }
    return res;
  }
  // debug
  friend ostream &operator<<(ostream &s, UnionFind uf) {
    const vector<vector<int>> &gs = uf.groups();
    for (const vector<int> &g : gs) {
      s << "group: ";
      for (int v : g) s << v << " ";
      s << endl;
    }
    return s;
  }
};
// Lazy Segment Tree
template <class Monoid, class Action>
struct LazySegmentTree {
  // various function types
  using FuncOperator = function<Monoid(Monoid, Monoid)>;
  using FuncMapping = function<Monoid(Action, Monoid)>;
  using FuncComposition = function<Action(Action, Action)>;
  // core member
  int N;
  FuncOperator OP;
  FuncMapping MAPPING;
  FuncComposition COMPOSITION;
  Monoid IDENTITY_MONOID;
  Action IDENTITY_ACTION;
  // inner data
  int log, offset;
  vector<Monoid> dat;
  vector<Action> lazy;
  // constructor
  LazySegmentTree() {}
  LazySegmentTree(int n, const FuncOperator op, const FuncMapping mapping,
                  const FuncComposition composition,
                  const Monoid &identity_monoid,
                  const Action &identity_action) {
    init(n, op, mapping, composition, identity_monoid, identity_action);
  }
  LazySegmentTree(const vector<Monoid> &v, const FuncOperator op,
                  const FuncMapping mapping, const FuncComposition composition,
                  const Monoid &identity_monoid,
                  const Action &identity_action) {
    init(v, op, mapping, composition, identity_monoid, identity_action);
  }
  void init(int n, const FuncOperator op, const FuncMapping mapping,
            const FuncComposition composition, const Monoid &identity_monoid,
            const Action &identity_action) {
    N = n, OP = op, MAPPING = mapping, COMPOSITION = composition;
    IDENTITY_MONOID = identity_monoid, IDENTITY_ACTION = identity_action;
    log = 0, offset = 1;
    while (offset < N) ++log, offset <<= 1;
    dat.assign(offset * 2, IDENTITY_MONOID);
    lazy.assign(offset * 2, IDENTITY_ACTION);
  }
  void init(const vector<Monoid> &v, const FuncOperator op,
            const FuncMapping mapping, const FuncComposition composition,
            const Monoid &identity_monoid, const Action &identity_action) {
    init((int)v.size(), op, mapping, composition, identity_monoid,
         identity_action);
    build(v);
  }
  void build(const vector<Monoid> &v) {
    assert(N == (int)v.size());
    for (int i = 0; i < N; ++i) dat[i + offset] = v[i];
    for (int k = offset - 1; k > 0; --k) pull_dat(k);
  }
  int size() const { return N; }
  // basic functions for lazy segment tree
  void pull_dat(int k) { dat[k] = OP(dat[k * 2], dat[k * 2 + 1]); }
  void apply_lazy(int k, const Action &f) {
    dat[k] = MAPPING(f, dat[k]);
    if (k < offset) lazy[k] = COMPOSITION(f, lazy[k]);
  }
  void push_lazy(int k) {
    apply_lazy(k * 2, lazy[k]);
    apply_lazy(k * 2 + 1, lazy[k]);
    lazy[k] = IDENTITY_ACTION;
  }
  void pull_dat_deep(int k) {
    for (int h = 1; h <= log; ++h) pull_dat(k >> h);
  }
  void push_lazy_deep(int k) {
    for (int h = log; h >= 1; --h) push_lazy(k >> h);
  }
  // setter and getter, update A[i], i is 0-indexed, O(log N)
  void set(int i, const Monoid &v) {
    assert(0 <= i && i < N);
    int k = i + offset;
    push_lazy_deep(k);
    dat[k] = v;
    pull_dat_deep(k);
  }
  Monoid get(int i) {
    assert(0 <= i && i < N);
    int k = i + offset;
    push_lazy_deep(k);
    return dat[k];
  }
  Monoid operator[](int i) { return get(i); }
  // apply f for index i
  void apply(int i, const Action &f) {
    assert(0 <= i && i < N);
    int k = i + offset;
    push_lazy_deep(k);
    dat[k] = MAPPING(f, dat[k]);
    pull_dat_deep(k);
  }
  // apply f for interval [l, r)
  void apply(int l, int r, const Action &f) {
    assert(0 <= l && l <= r && r <= N);
    if (l == r) return;
    l += offset, r += offset;
    for (int h = log; h >= 1; --h) {
      if (((l >> h) << h) != l) push_lazy(l >> h);
      if (((r >> h) << h) != r) push_lazy((r - 1) >> h);
    }
    int original_l = l, original_r = r;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) apply_lazy(l++, f);
      if (r & 1) apply_lazy(--r, f);
    }
    l = original_l, r = original_r;
    for (int h = 1; h <= log; ++h) {
      if (((l >> h) << h) != l) pull_dat(l >> h);
      if (((r >> h) << h) != r) pull_dat((r - 1) >> h);
    }
  }
  // get prod of interval [l, r)
  Monoid prod(int l, int r) {
    assert(0 <= l && l <= r && r <= N);
    if (l == r) return IDENTITY_MONOID;
    l += offset, r += offset;
    for (int h = log; h >= 1; --h) {
      if (((l >> h) << h) != l) push_lazy(l >> h);
      if (((r >> h) << h) != r) push_lazy(r >> h);
    }
    Monoid val_left = IDENTITY_MONOID, val_right = IDENTITY_MONOID;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) val_left = OP(val_left, dat[l++]);
      if (r & 1) val_right = OP(dat[--r], val_right);
    }
    return OP(val_left, val_right);
  }
  Monoid all_prod() { return dat[1]; }
  // get max r such that f(v) = True (v = prod(l, r)), O(log N)
  // f(IDENTITY) need to be True
  int max_right(const function<bool(Monoid)> f, int l = 0) {
    if (l == N) return N;
    l += offset;
    push_lazy_deep(l);
    Monoid sum = IDENTITY_MONOID;
    do {
      while (l % 2 == 0) l >>= 1;
      if (!f(OP(sum, dat[l]))) {
        while (l < offset) {
          push_lazy(l);
          l = l * 2;
          if (f(OP(sum, dat[l]))) {
            sum = OP(sum, dat[l]);
            ++l;
          }
        }
        return l - offset;
      }
      sum = OP(sum, dat[l]);
      ++l;
    } while ((l & -l) != l);  // stop if l = 2^e
    return N;
  }
  // get min l that f(get(l, r)) = True (0-indexed), O(log N)
  // f(IDENTITY) need to be True
  int min_left(const function<bool(Monoid)> f, int r = -1) {
    if (r == 0) return 0;
    if (r == -1) r = N;
    r += offset;
    push_lazy_deep(r - 1);
    Monoid sum = IDENTITY_MONOID;
    do {
      --r;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!f(OP(dat[r], sum))) {
        while (r < offset) {
          push_lazy(r);
          r = r * 2 + 1;
          if (f(OP(dat[r], sum))) {
            sum = OP(dat[r], sum);
            --r;
          }
        }
        return r + 1 - offset;
      }
      sum = OP(dat[r], sum);
    } while ((r & -r) != r);
    return 0;
  }
  // debug stream
  friend ostream &operator<<(ostream &s, LazySegmentTree seg) {
    for (int i = 0; i < (int)seg.size(); ++i) {
      s << seg[i];
      if (i != (int)seg.size() - 1) s << " ";
    }
    return s;
  }
  // dump
  void dump() {
    for (int i = 0; i <= log; ++i) {
      for (int j = (1 << i); j < (1 << (i + 1)); ++j) {
        cout << "{" << dat[j] << "," << lazy[j] << "} ";
      }
      cout << endl;
    }
  }
};
// modint
template <int MOD>
struct Fp {
  // inner value
  long long val;
  // constructor
  constexpr Fp() : val(0) {}
  constexpr Fp(long long v) : val(v % MOD) {
    if (val < 0) val += MOD;
  }
  // getter
  constexpr long long get() const { return val; }
  constexpr int get_mod() const { return MOD; }
  // comparison operators
  constexpr bool operator==(const Fp &r) const { return this->val == r.val; }
  constexpr bool operator!=(const Fp &r) const { return this->val != r.val; }
  // arithmetic operators
  constexpr Fp &operator+=(const Fp &r) {
    val += r.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  constexpr Fp &operator-=(const Fp &r) {
    val -= r.val;
    if (val < 0) val += MOD;
    return *this;
  }
  constexpr Fp &operator*=(const Fp &r) {
    val = val * r.val % MOD;
    return *this;
  }
  constexpr Fp &operator/=(const Fp &r) {
    long long a = r.val, b = MOD, u = 1, v = 0;
    while (b) {
      long long t = a / b;
      a -= t * b, swap(a, b);
      u -= t * v, swap(u, v);
    }
    val = val * u % MOD;
    if (val < 0) val += MOD;
    return *this;
  }
  constexpr Fp operator+() const { return Fp(*this); }
  constexpr Fp operator-() const { return Fp(0) - Fp(*this); }
  constexpr Fp operator+(const Fp &r) const { return Fp(*this) += r; }
  constexpr Fp operator-(const Fp &r) const { return Fp(*this) -= r; }
  constexpr Fp operator*(const Fp &r) const { return Fp(*this) *= r; }
  constexpr Fp operator/(const Fp &r) const { return Fp(*this) /= r; }
  // other operators
  constexpr Fp &operator++() {
    ++val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  constexpr Fp &operator--() {
    if (val == 0) val += MOD;
    --val;
    return *this;
  }
  constexpr Fp operator++(int) {
    Fp res = *this;
    ++*this;
    return res;
  }
  constexpr Fp operator--(int) {
    Fp res = *this;
    --*this;
    return res;
  }
  friend constexpr istream &operator>>(istream &is, Fp<MOD> &x) {
    is >> x.val;
    x.val %= MOD;
    if (x.val < 0) x.val += MOD;
    return is;
  }
  friend constexpr ostream &operator<<(ostream &os, const Fp<MOD> &x) {
    return os << x.val;
  }
  // other functions
  constexpr Fp pow(long long n) const {
    Fp res(1), mul(*this);
    while (n > 0) {
      if (n & 1) res *= mul;
      mul *= mul;
      n >>= 1;
    }
    return res;
  }
  constexpr Fp inv() const {
    Fp res(1), div(*this);
    return res / div;
  }
  friend constexpr Fp<MOD> pow(const Fp<MOD> &r, long long n) {
    return r.pow(n);
  }
  friend constexpr Fp<MOD> inv(const Fp<MOD> &r) { return r.inv(); }
};
// Segment Tree
template <class Monoid>
struct SegmentTree {
  using Func = function<Monoid(Monoid, Monoid)>;
  // core member
  int N;
  Func OP;
  Monoid IDENTITY;
  // inner data
  int log, offset;
  vector<Monoid> dat;
  // constructor
  SegmentTree() {}
  SegmentTree(int n, const Func &op, const Monoid &identity) {
    init(n, op, identity);
  }
  SegmentTree(const vector<Monoid> &v, const Func &op, const Monoid &identity) {
    init(v, op, identity);
  }
  void init(int n, const Func &op, const Monoid &identity) {
    N = n;
    OP = op;
    IDENTITY = identity;
    log = 0, offset = 1;
    while (offset < N) ++log, offset <<= 1;
    dat.assign(offset * 2, IDENTITY);
  }
  void init(const vector<Monoid> &v, const Func &op, const Monoid &identity) {
    init((int)v.size(), op, identity);
    build(v);
  }
  void pull(int k) { dat[k] = OP(dat[k * 2], dat[k * 2 + 1]); }
  void build(const vector<Monoid> &v) {
    assert(N == (int)v.size());
    for (int i = 0; i < N; ++i) dat[i + offset] = v[i];
    for (int k = offset - 1; k > 0; --k) pull(k);
  }
  void clear() { dat.assign(dat.size(), IDENTITY); }
  int size() const { return N; }
  Monoid operator[](int i) const { return dat[i + offset]; }
  // update A[i], i is 0-indexed, O(log N)
  void set(int i, const Monoid &v) {
    assert(0 <= i && i < N);
    int k = i + offset;
    dat[k] = v;
    while (k >>= 1) pull(k);
  }
  // get [l, r), l and r are 0-indexed, O(log N)
  Monoid prod(int l, int r) {
    assert(0 <= l && l <= r && r <= N);
    Monoid val_left = IDENTITY, val_right = IDENTITY;
    l += offset, r += offset;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) val_left = OP(val_left, dat[l++]);
      if (r & 1) val_right = OP(dat[--r], val_right);
    }
    return OP(val_left, val_right);
  }
  Monoid all_prod() { return dat[1]; }
  // get max r such that f(v) = True (v = prod(l, r)), O(log N)
  // f(IDENTITY) need to be True
  int max_right(const function<bool(Monoid)> f, int l = 0) {
    if (l == N) return N;
    l += offset;
    Monoid sum = IDENTITY;
    do {
      while (l % 2 == 0) l >>= 1;
      if (!f(OP(sum, dat[l]))) {
        while (l < offset) {
          l = l * 2;
          if (f(OP(sum, dat[l]))) {
            sum = OP(sum, dat[l]);
            ++l;
          }
        }
        return l - offset;
      }
      sum = OP(sum, dat[l]);
      ++l;
    } while ((l & -l) != l);  // stop if l = 2^e
    return N;
  }
  // get min l that f(get(l, r)) = True (0-indexed), O(log N)
  // f(IDENTITY) need to be True
  int min_left(const function<bool(Monoid)> f, int r = -1) {
    if (r == 0) return 0;
    if (r == -1) r = N;
    r += offset;
    Monoid sum = IDENTITY;
    do {
      --r;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!f(OP(dat[r], sum))) {
        while (r < offset) {
          r = r * 2 + 1;
          if (f(OP(dat[r], sum))) {
            sum = OP(dat[r], sum);
            --r;
          }
        }
        return r + 1 - offset;
      }
      sum = OP(dat[r], sum);
    } while ((r & -r) != r);
    return 0;
  }
  // debug
  friend ostream &operator<<(ostream &s, const SegmentTree &seg) {
    for (int i = 0; i < (int)seg.size(); ++i) {
      s << seg[i];
      if (i != (int)seg.size() - 1) s << " ";
    }
    return s;
  }
};
int main() {
  // endlの代わりに'\n'を使うと高速化できる
  // これがないと落ちることがある
  // 1<<iに注意！
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ll n, f;
  cin >> n >> f;
  vector<ll> a(n), b(n), c(n);
  for (ll i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (ll i = 0; i < n; i++) {
    cin >> b[i];
  }
  for (ll i = 0; i < n; i++) {
    cin >> c[i];
  }
  auto cur = bitset<900001>(1);
  for (ll i = 0; i < n; i++) {
    auto cru1 = cur << a[i];
    auto cru2 = cur << b[i];
    auto cru3 = cur << c[i];
    cur = cru1 | cru2 | cru3;
    cout << cur.count() << '\n';
  }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0