oj.uz

Submission #777421

# Submission time Handle Problem Language Result Execution time Memory
777421 2023-07-09T08:24:40 Z alexander707070 Digital Circuit (IOI22_circuit) C++17
16 / 100
 850 ms 21948 KB 
#include<bits/stdc++.h>
#define MAXN 800007
using namespace std;

const long long mod=1000002022;

int n,m;
long long black[MAXN],white[MAXN];
long long prod[MAXN],total,diff,zeros;
vector<int> v[MAXN];

void dfs(int x){
    if(v[x].size()==0){
        prod[x]=1; return;
    }

    prod[x]=1;
    for(int i=0;i<v[x].size();i++){
        dfs(v[x][i]);
        prod[x]*=prod[v[x][i]];
        prod[x]%=mod;
    }
    prod[x]*=2; prod[x]%=mod;

    black[x]=0;
    /* c=2 */ black[x]+=black[v[x][0]]*black[v[x][1]];
    /* c=1 */ black[x]+=black[v[x][0]]*black[v[x][1]]+black[v[x][0]]*white[v[x][1]]+white[v[x][0]]*black[v[x][1]];
    black[x]%=mod;

    white[x]=(prod[x]-black[x]+mod)%mod;
}

long long power(long long x,int y){
    if(y==0)return 1;
    return (power(x,y-1)*x)%mod;
}

int lg(int x){
    if(x==1)return 0;
    return lg(x/2)+1;
}

int tree[MAXN],lazy[MAXN];

void psh(int v,int l,int r){
    if(lazy[v]==0)return;
    int tt=(l+r)/2;

    tree[2*v]=(tt-l+1)-tree[2*v];
    lazy[2*v]^=1; 
    
    tree[2*v+1]=(r-(tt+1)+1)-tree[2*v+1];
    lazy[2*v+1]^=1;

    lazy[v]=0;
}

void update(int v,int l,int r,int ll,int rr){
    if(ll>rr)return;
    if(l==ll and r==rr){
        tree[v]=(r-l+1)-tree[v];
        lazy[v]^=1;
    }else{
        int tt=(l+r)/2;
        psh(v,l,r);

        update(2*v,l,tt,ll,min(tt,rr));
        update(2*v+1,tt+1,r,max(tt+1,ll),rr);

        tree[v]=tree[2*v]+tree[2*v+1];
    }
}

void init(int N, int M,vector<int> P,vector<int> A){
    n=N; m=M;
    total=power(2,N);
    diff=power(2,N-lg(N+1));

    for(int i=0;i<M;i++){
        if(A[i]==1)update(1,0,M-1,i,i);
    }
}

int count_ways(int L, int R){
    L-=n; R-=n;
    update(1,0,m-1,L,R);
    zeros=m-tree[1];

    return (total-(diff*zeros)+mod*zeros)%mod;
}

/*
int main(){
    init(15, 16, {-1, 0, 0, 1, 1, 2, 2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1});
    cout<<count_ways(15,29)<<"\n";
}
*/

Compilation message

circuit.cpp: In function 'void dfs(int)':
circuit.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19024 KB Output is correct
2 Incorrect 9 ms 19052 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19064 KB Output is correct
2 Correct 10 ms 19100 KB Output is correct
3 Correct 9 ms 19112 KB Output is correct
4 Correct 9 ms 19008 KB Output is correct
5 Correct 9 ms 19068 KB Output is correct
6 Incorrect 11 ms 19096 KB 1st lines differ - on the 1st token, expected: '706880838', found: '570720026'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19024 KB Output is correct
2 Incorrect 9 ms 19052 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 20516 KB Output is correct
2 Correct 711 ms 21948 KB Output is correct
3 Correct 584 ms 21940 KB Output is correct
4 Correct 803 ms 21172 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 20516 KB Output is correct
2 Correct 711 ms 21948 KB Output is correct
3 Correct 584 ms 21940 KB Output is correct
4 Correct 803 ms 21172 KB Output is correct
5 Correct 494 ms 20512 KB Output is correct
6 Correct 745 ms 21912 KB Output is correct
7 Correct 764 ms 21908 KB Output is correct
8 Correct 850 ms 21916 KB Output is correct
9 Correct 405 ms 19152 KB Output is correct
10 Correct 712 ms 19236 KB Output is correct
11 Correct 757 ms 19280 KB Output is correct
12 Correct 737 ms 19228 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19064 KB Output is correct
2 Correct 10 ms 19100 KB Output is correct
3 Correct 9 ms 19112 KB Output is correct
4 Correct 9 ms 19008 KB Output is correct
5 Correct 9 ms 19068 KB Output is correct
6 Incorrect 11 ms 19096 KB 1st lines differ - on the 1st token, expected: '706880838', found: '570720026'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19024 KB Output is correct
2 Incorrect 9 ms 19052 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19024 KB Output is correct
2 Incorrect 9 ms 19052 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
3 Halted 0 ms 0 KB -