Submission #1238575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238575		MarwenElarbi	Digital Circuit (IOI22_circuit)	C++17	0 / 100	6 ms	1288 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int nax=2005;
const int MOD = 1e9 + 2022 ;
int a[nax];
long long dp[2][nax];
int n,m;
void merge(int pos){
    dp[0][pos]=dp[0][pos*2+1]*dp[1][pos*2+2]+dp[1][pos*2+1]*dp[0][pos*2+2]+dp[0][pos*2+1]*dp[0][pos*2+2]*2;
    dp[1][pos]=dp[0][pos*2+1]*dp[1][pos*2+2]+dp[1][pos*2+1]*dp[0][pos*2+2]+dp[1][pos*2+1]*dp[1][pos*2+2]*2;
    dp[0][pos]%=MOD;
    dp[1][pos]%=MOD;
}
void build(int pos,int l,int r){
    if(l==r){
        dp[a[l]][l]=1;
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    merge(pos);
}
void update(int pos,int l,int r,int idx){
    if(l==r){
        dp[a[l]][pos]=0;
        a[l]^=1;
        dp[a[l]][pos]=1;
        return;
    }
    int mid=(r+l)/2;
    if(idx<=mid) update(pos*2+1,l,mid,idx);
    else update(pos*2+2,mid+1,r,idx);
    merge(pos);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A){
    n=N;m=M;
    for (int i = 0; i < M; ++i) a[i]=A[i];
    build(0,0,m-1);
}

int count_ways(int L, int R) {
    L-=n;R-=n;
    update(0,0,m-1,L);
    return dp[1][0];
}

• 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