Submission #1058125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058125		noyancanturk	Digital Circuit (IOI22_circuit)	C++17	0 / 100	7 ms	3024 KiB

circuit

#include "circuit.h"

#include<bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;

using lint=long long;

lint mod=1000002022;

int sum(lint i,lint j){
  if(i+j<mod)return i+j;
  return i+j-mod;
}

int sub(lint i,lint j){
  if(j<=i)return i-j;
  return i-j+mod;
}

int mul(lint i,lint j){
  return i*j%mod;
}

int n,m;
bool flag=1;

const int lim=2e5+100;

vector<int>p,a;
int can[lim],cant[lim];

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n=N,m=M;
  p=P,a=A;
  for(int i=1;i<n+m;i++){
    if(p[i]!=(i-1)/2){
      flag=0;
    }
  }
  if(flag){
    for(int i=0;i<m;i++){
      can[n+i]=a[i];
      cant[n+i]=!a[i];
    }
    for(int i=n-1;0<=i;i--){
      can[i]=sum(mul(2*can[2*i+1],can[2*i+2]),sum(mul(can[2*i+1],cant[2*i+2]),mul(cant[2*i+1],can[2*i+2])));
      cant[i]=sum(mul(2*cant[2*i+1],cant[2*i+2]),sum(mul(can[2*i+1],cant[2*i+2]),mul(cant[2*i+1],can[2*i+2])));
    }
  }
}

int count_ways(int L, int R) {
  if(flag){
    assert(L==R);
    swap(can[L+n],cant[L+n]);
    int i=p[L+n];
    while(i!=-1){
      //cerr<<"updateing "<<i<<" :: "<<2*i+1<<" "<<2*i+2<<"\n";
      can[i]=sum(mul(2*can[2*i+1],can[2*i+2]),sum(mul(can[2*i+1],cant[2*i+2]),mul(cant[2*i+1],can[2*i+2])));
      cant[i]=sum(mul(2*cant[2*i+1],cant[2*i+2]),sum(mul(can[2*i+1],cant[2*i+2]),mul(cant[2*i+1],can[2*i+2])));
      i=p[i];
    }
    /*
    for(int i=0;i<n+m;i++){
      cerr<<i<<" :: "<<can[i]<<" "<<cant[i]<<"\n";
    }cerr<<"\n";
    */
    return can[0];
  }
  return -1;
}

• Subtask 1: 0 / 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