oj.uz

Submission #1110081

# Submission time Handle Problem Language Result Execution time Memory
1110081 2024-11-08T16:27:06 Z ASN49K Digital Circuit (IOI22_circuit) C++17
23 / 100
 2074 ms 17992 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
    test_mare=(__builtin_popcount(m)==1);
    for(int i=1;i<n+m;i++)
    {
        test_mare&=(pp[i]==(i-1)/2);
    }
    assert(test_mare  || max(n,m)<=5000);
    if(test_mare)
    {
        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);
        }
        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(test_mare)
    {
        if(l<=r)
        {
            update(0,0,m-1,l,r);
        }
    }
    else
    {
        for(int i=l;i<=r;i++)
        {
            a[i]^=1;
        }
        dfs(0);
    }

    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 1 ms 6480 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 2 ms 6904 KB Output is correct
4 Correct 2 ms 6736 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Correct 2 ms 6904 KB Output is correct
7 Correct 2 ms 6736 KB Output is correct
8 Correct 3 ms 6736 KB Output is correct
9 Correct 3 ms 6736 KB Output is correct
10 Correct 2 ms 6736 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 3 ms 6736 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct
2 Incorrect 1 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 1378 ms 7504 KB Output is correct
2 Correct 2023 ms 8272 KB Output is correct
3 Correct 2041 ms 8264 KB Output is correct
4 Correct 1940 ms 8272 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1378 ms 7504 KB Output is correct
2 Correct 2023 ms 8272 KB Output is correct
3 Correct 2041 ms 8264 KB Output is correct
4 Correct 1940 ms 8272 KB Output is correct
5 Correct 1649 ms 7504 KB Output is correct
6 Correct 2074 ms 8264 KB Output is correct
7 Correct 2059 ms 8272 KB Output is correct
8 Correct 1988 ms 8272 KB Output is correct
9 Correct 1022 ms 6736 KB Output is correct
10 Correct 2001 ms 6736 KB Output is correct
11 Correct 1985 ms 6736 KB Output is correct
12 Correct 1935 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 2 ms 6480 KB Output is correct
3 Correct 2 ms 6904 KB Output is correct
4 Correct 2 ms 6736 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Correct 2 ms 6904 KB Output is correct
7 Correct 2 ms 6736 KB Output is correct
8 Correct 3 ms 6736 KB Output is correct
9 Correct 3 ms 6736 KB Output is correct
10 Correct 2 ms 6736 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 3 ms 6736 KB Output is correct
13 Correct 1378 ms 7504 KB Output is correct
14 Correct 2023 ms 8272 KB Output is correct
15 Correct 2041 ms 8264 KB Output is correct
16 Correct 1940 ms 8272 KB Output is correct
17 Correct 1649 ms 7504 KB Output is correct
18 Correct 2074 ms 8264 KB Output is correct
19 Correct 2059 ms 8272 KB Output is correct
20 Correct 1988 ms 8272 KB Output is correct
21 Correct 1022 ms 6736 KB Output is correct
22 Correct 2001 ms 6736 KB Output is correct
23 Correct 1985 ms 6736 KB Output is correct
24 Correct 1935 ms 6736 KB Output is correct
25 Runtime error 31 ms 17992 KB Execution killed with signal 6
26 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 1 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 1 ms 6480 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -