oj.uz

Submission #1110065

# Submission time Handle Problem Language Result Execution time Memory
1110065 2024-11-08T15:42:57 Z ASN49K Digital Circuit (IOI22_circuit) C++17
16 / 100
 2098 ms 8284 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

const int N=100'000,mod=1e9+2022;
int add(int x,int y)
{
    return (x+y)%mod;
}
void add_self(int& x,int y)
{
    x+=y;
    if(x>=mod)
    {
        x-=mod;
    }
    if(x<0)
    {
        x+=mod;
    }
}
int prod(int x,int y)
{
    return (1LL*x*y)%mod;
}
int n,m;
vector<int>g[2*N],a;
bool lazy[2*N];
int dp[2*N][2];
bool test_mare;


void push_down(int nod)
{
    if(lazy[nod])
    {
        swap(dp[2*nod+1][0] , dp[2*nod+1][1]);
        swap(dp[2*nod+2][0] , dp[2*nod+2][1]);
        lazy[2*nod+1]^=true;
        lazy[2*nod+2]^=true;
        lazy[nod]=false;
    }
}
void recalc(int nod)
{
    int l=2*nod+1,r=2*nod+2;
    //dp[nod][0]=dp[nod][1]=0;
    dp[nod][1]=add(add(prod(dp[l][0],dp[r][1]) , prod(dp[l][1],dp[r][0])) , prod(2,prod(dp[l][1],dp[r][1])));
    dp[nod][0]=add(add(prod(dp[l][0],dp[r][1]) , prod(dp[l][1],dp[r][0])) , prod(2,prod(dp[l][0],dp[r][0])));
}
void update(int nod,int st,int dr,int l,int r)
{
    if(st>r || dr<l)
    {
        return;
    }
    if(l<=st && dr<=r)
    {
        lazy[nod]^=true;
        swap(dp[nod][0] , dp[nod][1]);
        return;
    }
    int m=(st+dr)/2;
    push_down(nod);
    update(2*nod+1,st,m,l,r);
    update(2*nod+2,m+1,dr,l,r);
    recalc(nod);
}
void init(int nn, int mm, std::vector<int> pp, std::vector<int> init_a)
{
    n=nn;
    m=mm;
    //schimbat n mare
    if(n)
    {
        test_mare=true;
        for(int i=0;i<m;i++)
        {
            dp[n+i][0]=(init_a[i]==0);
            dp[n+i][1]=(init_a[i]==1);
        }

        for(int i=n-1;i>=0;i--)
        {
            recalc(i);
        }
        //cerr<<"da";
        return;
    }
    for(int i=1;i<n+m;i++)
    {
        g[pp[i]].push_back(i);
    }
    a=init_a;
}

void dfs(int nod)
{
    for(auto &c:g[nod])
    {
        dfs(c);
    }
    int sz=(int)g[nod].size();
    if(g[nod].empty())
    {
        dp[nod][0]=(a[nod-n]==0);
        dp[nod][1]=(a[nod-n]==1);
        return;
    }
    vector<int>choose(sz+1,0);
    choose[0]=1;
    for(auto &c:g[nod])
    {
        for(int i=sz;i>=0;i--)
        {
            choose[i]=prod(choose[i] , dp[c][0]);
            if(i>0)
            {
                add_self(choose[i] , prod(choose[i-1] , dp[c][1]));
            }
        }
    }
    dp[nod][0]=dp[nod][1]=0;
    for(int i=1;i<=sz;i++)
    {
        add_self(dp[nod][0] , prod(choose[i],sz-i));
        add_self(dp[nod][1] , prod(choose[i],i));
    }
    add_self(dp[nod][0],prod(choose[0],sz));
}
int count_ways(int l, int r)
{
    l-=n;
    r-=n;
    if(l<=r)
    {
        update(0,0,m-1,l,r);
    }
    return dp[0][1];
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct
2 Correct 3 ms 6736 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 2 ms 6736 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Incorrect 2 ms 6736 KB 1st lines differ - on the 1st token, expected: '706880838', found: '320694190'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1376 ms 7632 KB Output is correct
2 Correct 1970 ms 8284 KB Output is correct
3 Correct 1954 ms 8264 KB Output is correct
4 Correct 1956 ms 8264 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1376 ms 7632 KB Output is correct
2 Correct 1970 ms 8284 KB Output is correct
3 Correct 1954 ms 8264 KB Output is correct
4 Correct 1956 ms 8264 KB Output is correct
5 Correct 1636 ms 7504 KB Output is correct
6 Correct 2085 ms 8272 KB Output is correct
7 Correct 2072 ms 8272 KB Output is correct
8 Correct 2098 ms 8272 KB Output is correct
9 Correct 989 ms 6736 KB Output is correct
10 Correct 1954 ms 6736 KB Output is correct
11 Correct 2009 ms 6736 KB Output is correct
12 Correct 1954 ms 6736 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct
2 Correct 3 ms 6736 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 2 ms 6736 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Incorrect 2 ms 6736 KB 1st lines differ - on the 1st token, expected: '706880838', found: '320694190'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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