Submission #1230438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230438		Malix	Digital Circuit (IOI22_circuit)	C++20	18 / 100	3076 ms	2162688 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<ll,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1000002022;

int n,m;
vi a,p,ch;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n=N;m=M;a=A;p=P;
  ch.resize(n+m,0);
  REP(i,1,n+m)ch[p[i]]++;
  return;
}

int count_ways(int L, int R) {
  vector<vector<ll>> dp(n+m,vector<ll>(n+m,0)),dp2(n+m,vector<ll>(2,0));
  REP(i,L-n,R-n+1)a[i]=1-a[i];
  REP(i,n,n+m)dp2[i][a[i-n]]++;
  REP(i,0,n)dp[i][0]=1;
  for(int i=n+m-1;i>=0;i--){
    int x=ch[i];
    vector<ll> b=dp[i],c=dp[i];
    REP(j,1,x+1){
      b[j]+=b[j-1];
      b[j]%=M;
    }
    for(int j=x-1;j>=0;j--){
      c[j]+=c[j+1];
      c[j]%=M;
    }
    REP(j,0,x+1){
      if(j!=0)dp2[i][1]+=c[j];
      if(j!=x)dp2[i][0]+=b[j];
      dp2[i][1]%=M;
      dp2[i][0]%=M;
    }
    if(i==0)break;
    int k=p[i];
    for(int j=n+m-1;j>=0;j--){
      if(j!=n+m-1){
        dp[k][j+1]+=dp[k][j]*dp2[i][1];
        dp[k][j+1]%=M;
      }
      dp[k][j]*=dp2[i][0];
      dp[k][j]%=M;
    }
  }
  return (int)dp2[0][1];
}

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