oj.uz

Submission #627206

# Submission time Handle Problem Language Result Execution time Memory
627206 2022-08-12T11:20:28 Z model_code Digital Circuit (IOI22_circuit) C++17
16 / 100
 1254 ms 2900 KB 
// failed/solution-prabowo-perfect-binary.cpp
// O(N + M + Q log M)

#include "circuit.h"

#include <algorithm>
#include <utility>
#include <vector>

const int kMod = 1000002022;

int N, M;
std::vector<int> dp0, dp1;
std::vector<bool> flip;

void compute(int u) {
  int l = u * 2 + 1, r = u * 2 + 2;
  int diff = (1LL * dp0[l] * dp1[r] + 1LL * dp1[l] * dp0[r]) % kMod;
  dp0[u] = (2LL * dp0[l] * dp0[r] + diff) % kMod;
  dp1[u] = (2LL * dp1[l] * dp1[r] + diff) % kMod;
}

void init(int _N, int _M, std::vector<int>, std::vector<int> A) {
  N = _N; M = _M;
  dp0.resize(N + M);
  dp1.resize(N + M);
  flip.resize(N + M);
  for (int i = N; i < N + M; ++i) {
    if (A[i - N]) {
      dp1[i] = 1;
    } else {
      dp0[i] = 1;
    }
  }

  for (int i = N - 1; i >= 0; --i) {
    compute(i);
  }
}

void update(int node, int l, int r, int ll, int rr) {
  if (l >= rr || r <= ll) return;
  if (l >= ll && r <= rr) {
    flip[node] = !flip[node];
    std::swap(dp0[node], dp1[node]);
    return;
  }
  int lnode = node * 2 + 1;
  int rnode = node * 2 + 2;
  if (flip[node]) {
    flip[node] = false;
    std::swap(dp0[lnode], dp1[lnode]);
    flip[lnode] = !flip[lnode];
    std::swap(dp0[rnode], dp1[rnode]);
    flip[rnode] = !flip[rnode];
  }

  int mid = (l + r) / 2;
  update(lnode, l, mid, ll, rr);
  update(rnode, mid, r, ll, rr);
  compute(node);
}

void update(int l, int r) {
  update(0, 0, M, l, r);
}

int count_ways(int L, int R) {
  L -= N; R -= N;
  update(L, R + 1);
  return dp1[0];
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 236 KB Output is correct
2 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 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 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '706880838', found: '771166560'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 1560 KB Output is correct
2 Correct 1014 ms 2900 KB Output is correct
3 Correct 897 ms 2872 KB Output is correct
4 Correct 1040 ms 2844 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 1560 KB Output is correct
2 Correct 1014 ms 2900 KB Output is correct
3 Correct 897 ms 2872 KB Output is correct
4 Correct 1040 ms 2844 KB Output is correct
5 Correct 732 ms 1508 KB Output is correct
6 Correct 1243 ms 2888 KB Output is correct
7 Correct 1108 ms 2872 KB Output is correct
8 Correct 1254 ms 2880 KB Output is correct
9 Correct 420 ms 336 KB Output is correct
10 Correct 971 ms 336 KB Output is correct
11 Correct 955 ms 336 KB Output is correct
12 Correct 873 ms 368 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 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '706880838', found: '771166560'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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