oj.uz

Submission #628386

# Submission time Handle Problem Language Result Execution time Memory
628386 2022-08-13T11:10:07 Z c28dnv9q3 Digital Circuit (IOI22_circuit) C++17
7 / 100
 3000 ms 2097152 KB 
#include "circuit.h"
#include <vector>
#include <cstdio>

using namespace std;
using ll = long long;

// N ... num threshold gates
// M ... num source gates

vector<int> A;
int N, M;
const int MOD = 1000002022;
vector<vector<int>> tree;

void init(int N, int M, vector<int> P, vector<int> A) {
  ::A = A;
  ::N = N;
  ::M = M;
  tree.resize(N);
  for (int i = 1; i < P.size(); i++)
    tree[P[i]].push_back(i);
}
ll mmod(ll v) {
  return ((v % MOD) + MOD) % MOD;
}

pair<ll,ll> countrec(int i) {
  if (i >= N) {
    if (A[i-N]) return {0, 1};
    else return {1, 0};
  }
  auto x = countrec(tree[i][0]);
  auto y = countrec(tree[i][1]);
  ll v = 0;
  // set 1
  v += x.second * y.first;
  v += x.first * y.second;
  v += x.second * y.second;
  // set 2
  v += x.second * y.second;
  
  ll tot = (x.first + x.second) * (y.first + y.second) * 2;
  // printf("%d -> %lld %lld\n", i, tot-v, v);
  return {mmod(tot-v), mmod(v)};
}

// toggle state of source gates between L and R (inclusive)
// return num distinctive param assignments with gate#0 = 1
int count_ways(int L, int R) {
  for (int i = L; i <= R; i++)
    A[i-N] = 1-A[i-N];
  
  return countrec(0).second;
}

Compilation message

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (int i = 1; i < P.size(); i++)
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Runtime error 957 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 268 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Runtime error 957 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3091 ms 2964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3091 ms 2964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 268 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Execution timed out 3091 ms 2964 KB Time limit exceeded
14 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 Runtime error 957 ms 2097152 KB Execution killed with signal 9
3 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 Runtime error 957 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -