Submission #786971

#	Time	Username	Problem	Language	Result	Execution time	Memory
786971		thimote75	디지털 회로 (IOI22_circuit)	C++17	2 / 100	3048 ms	1872 KiB

circuit

#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);

  int size_last = 0;
  num res       = 0;

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

    localC[target[i]] ++ ;
  }

  bool canAdd = false;
  for (int i = N - 1; i >= 0; i --) {
    if (localC[i] == C[i]) {
      if (i != 0) localC[i - 1] ++;
    } else 
      canAdd = true;

    if (canAdd) { res += localC[i] * Gamma[i + 1]; res %= MOD; }
  }

  if (!canAdd) return Gamma[0];

  return res;
}

Compilation message (stderr)

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

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