oj.uz

답안 #777421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777421 2023-07-09T08:24:40 Z alexander707070 디지털 회로 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -