Submission #815956

#	Time	Username	Problem	Language	Result	Execution time	Memory
815956		KoD	Digital Circuit (IOI22_circuit)	C++17	100 / 100	979 ms	15404 KiB

circuit

#include "circuit.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;

template <class F> struct make_fixed : private F {
  explicit make_fixed(F&& f) : F(std::forward<F>(f)) {}
  template <class... Args> decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <class T, class... Args> void DBG(const T& x, const Args&... args) {
  std::cerr << x;
  if constexpr (sizeof...(args)) {
    std::cerr << ' ';
    DBG(args...);
  } else {
    std::cerr << std::endl;
  }
}

template <class T> void DBG(const std::vector<T>& v) {
  std::cerr << '[';
  bool f = false;
  for (const T& x : v) {
    if (f) std::cerr << ", ";
    f = true;
    std::cerr << x;
  }
  std::cerr << ']' << std::endl;
}

constexpr int mod = 1000002022;

struct Fp {
  Fp() : x(0) {}
  Fp(int x) : x(x) {}

  Fp& operator+=(const Fp& t) {
    if ((x += t.x) >= mod) x -= mod;
    return *this;
  }
  Fp& operator-=(const Fp& t) {
    if ((x -= t.x) < 0) x += mod;
    return *this;
  }
  Fp& operator*=(const Fp& t) {
    x = (ll)x * t.x % mod;
    return *this;
  }

  Fp operator+(const Fp& t) const { return Fp(*this) += t; }
  Fp operator-(const Fp& t) const { return Fp(*this) -= t; }
  Fp operator*(const Fp& t) const { return Fp(*this) *= t; }

  int get() const { return x; }

  friend std::ostream& operator<<(std::ostream& os, const Fp& t) { return os << t.x; }

 private:
  int x;
};

struct segment_tree {
  segment_tree() = default;

  explicit segment_tree(vector<pair<Fp, Fp>> init) {
    logn = 0;
    while ((1 << logn) < (int)init.size()) logn += 1;
    size = 1 << logn;
    data.resize(2 * size);
    sub.resize(2 * size);
    flip.resize(size);
    for (int i = 0; i < (int)init.size(); ++i) std::tie(data[i + size], sub[i + size]) = init[i];
    for (int i = size - 1; i > 0; --i) fetch(i);
  }

  void range_flip(int l, int r) {
    l += size;
    r += size;
    push(l);
    push(r);
    for (int s = l, t = r; s < t; s >>= 1, t >>= 1) {
      if (s & 1) apply(s++);
      if (t & 1) apply(--t);
    }
    pull(l);
    pull(r);
  }

  Fp get() const { return data[1]; }

 private:
  int size, logn;
  vector<Fp> data, sub;
  vector<char> flip;

  void fetch(int i) {
    data[i] = data[2 * i] + data[2 * i + 1];
    sub[i] = sub[2 * i] + sub[2 * i + 1];
  }
  void apply(int i) {
    std::swap(data[i], sub[i]);
    if (i < size) flip[i] ^= 1;
  }
  void flush(int i) {
    if (flip[i]) {
      apply(2 * i);
      apply(2 * i + 1);
      flip[i] = false;
    }
  }
  void push(int i) {
    int rz = __builtin_ctz(i);
    for (int d = logn; d > rz; --d) flush(i >> d);
  }
  void pull(int i) {
    i >>= __builtin_ctz(i);
    while (i >>= 1) fetch(i);
  }
};

int N_memo;
segment_tree seg;

void init(int N, int M, vector<int> P, vector<int> A) {
  N_memo = N;
  vector<vector<int>> child(N + M);
  for (int i = 1; i < N + M; ++i) child[P[i]].push_back(i);
  vector<Fp> ways(N + M, 1);
  for (int i = N - 1; i >= 0; --i) {
    ways[i] = (int)child[i].size();
    for (const int j : child[i]) ways[i] *= ways[j];
  }
  vector<Fp> coeff(N + M, 1);
  for (int i = 0; i < N; ++i) {
    const int n = (int)child[i].size();
    vector<Fp> suff(n);
    suff[n - 1] = 1;
    for (int k = n - 1; k > 0; --k) suff[k - 1] = suff[k] * ways[child[i][k]];
    Fp pref = coeff[i];
    for (int k = 0; k < n; ++k) {
      coeff[child[i][k]] = pref * suff[k];
      pref *= ways[child[i][k]];
    }
  }
  vector<pair<Fp, Fp>> data(M);
  for (int i = 0; i < M; ++i) {
    if (A[i]) data[i] = {coeff[i + N], 0};
    else data[i] = {0, coeff[i + N]};
  }
  seg = segment_tree(std::move(data));
}

int count_ways(int L, int R) {
  seg.range_flip(L - N_memo, R - N_memo + 1);
  return seg.get().get();
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11