oj.uz

Submission #786991

# Submission time Handle Problem Language Result Execution time Memory
786991 2023-07-18T16:14:50 Z thimote75 Digital Circuit (IOI22_circuit) C++17
2 / 100
 3000 ms 1872 KB 
#include "circuit.h"

#include <bits/stdc++.h>
#define num long long

using namespace std;
const int MOD = 1000002022;

using idata = vector<signed>;
using ndata = vector<num>;

ndata C;
ndata Gamma;

idata status;
idata target;

int N, M;

void init(int _N, int _M, idata P, idata A) {
  N = _N; M = _M;
  C    .resize(N);
  Gamma.resize(N + 1, 1);

  status = A;
  target.resize(M);
  for (int i = 0; i < M; i ++)
    target[i] = P[i + N];

  for (int i = 1; i < N + M; i ++) C[P[i]] ++;

  for (int i = N - 1; i >= 0; i --) Gamma[i] = (C[i] * Gamma[i + 1]) % MOD;
}

int count_ways(int L, int R) {
  L -= N; R -= N;
  for (int i = L; i <= R; i ++)
    status [i] = 1 - status[i];
  
  idata localC(N);
  idata localD(N);

  int size_last = 0;
  num res       = 0;

  for (int i = 0; i < M; i ++) {
    if (status[i] == 0) continue ;

    localC[target[i]] ++;
  }

  num avec = localC[N - 1];
  num sans = C[N - 1] - localC[N - 1];
  if (sans == 0 && N != 1) localC[N - 2] ++;

  for (int i = N - 2; i >= 0; i --) {
    if (localC[i] == C[i]) {
      avec = Gamma[i];
      sans = 0;
      if (i != 0) localC[i - 1] ++;
      continue ;
    }
    avec = localC[i] * sans * Gamma[i + 1] + avec;
    avec %= MOD;
    sans = (C[i] - 1 - localC[i]) * Gamma[i + 1] + sans;
    sans %= MOD;
  }

  return avec;
}

Compilation message

circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:43:7: warning: unused variable 'size_last' [-Wunused-variable]
   43 |   int size_last = 0;
      |       ^~~~~~~~~
circuit.cpp:44:7: warning: unused variable 'res' [-Wunused-variable]
   44 |   num res       = 0;
      |       ^~~

Subtask #1
2.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 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 1872 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 3051 ms 1872 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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