oj.uz

Submission #815936

# Submission time Handle Problem Language Result Execution time Memory
815936 2023-08-09T02:44:30 Z KoD Digital Circuit (IOI22_circuit) C++17
16 / 100
 751 ms 9564 KB 
#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 < 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '8718'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '706889047'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '8718'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 4972 KB Output is correct
2 Correct 742 ms 9552 KB Output is correct
3 Correct 751 ms 9564 KB Output is correct
4 Correct 674 ms 9544 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 4972 KB Output is correct
2 Correct 742 ms 9552 KB Output is correct
3 Correct 751 ms 9564 KB Output is correct
4 Correct 674 ms 9544 KB Output is correct
5 Correct 489 ms 4896 KB Output is correct
6 Correct 685 ms 9524 KB Output is correct
7 Correct 686 ms 9544 KB Output is correct
8 Correct 579 ms 9540 KB Output is correct
9 Correct 347 ms 580 KB Output is correct
10 Correct 505 ms 848 KB Output is correct
11 Correct 736 ms 848 KB Output is correct
12 Correct 710 ms 848 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '706889047'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '8718'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '8718'
4 Halted 0 ms 0 KB -