oj.uz

Submission #1058125

# Submission time Handle Problem Language Result Execution time Memory
1058125 2024-08-14T08:37:18 Z noyancanturk Digital Circuit (IOI22_circuit) C++17
0 / 100
 7 ms 3024 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 3024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 3024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -