Submission #1057345

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1057345	2024-08-13T17:44:32 Z	sofijavelkovska	Digital Circuit (IOI22_circuit)	C++17	0 / 100	1440 ms	2097152 KB

circuit

#include "circuit.h"
//#include "stub.cpp"

#include <bits/stdc++.h>
using namespace std;

const int MOD=1000002022, MAXN=(1<<3);

// maxn maxn

int n, m;
vector<int> parent, a;
vector<int> adj[MAXN];
int subtree[2*MAXN];
long long factor[2*MAXN];
long long ones[2*MAXN-1], zeros[2*MAXN-1];
int lazy[2*MAXN-1]={0};

long long power(long long n, long long k)
{
    long long result=1, mul=n;
    for (int i=0; i<32; i++)
    {
        if (k&(1<<i))
            result=result*mul%MOD;
        mul=mul*mul%MOD;
    }

    return result;
}

void calcsize(int x)
{
    if (x>=n)
        subtree[x]=0;
    else
        subtree[x]=1;
    for (auto y : adj[x])
    {
        calcsize(y);
        subtree[x]=subtree[x]+subtree[y];
    }

    return;
}

void calcfactor(int x, long long current)
{
    if (x!=0)
        current=current*power(2, subtree[x])%MOD;
    factor[x]=current;
    for (auto y : adj[x])
        calcfactor(y, current);

    return;
}

void propagate(int x, int l, int r)
{
    if (r-l==1)
    {
        lazy[x]=0;
        return;
    }
    if (lazy[x]==0)
        return;
    swap(ones[2*x+1], zeros[2*x+1]);
    swap(ones[2*x+2], zeros[2*x+2]);
    lazy[2*x+1]=(lazy[2*x+1]+1)%2;
    lazy[2*x+2]=(lazy[2*x+2]+1)%2;
    lazy[x]=0;

    return;
}

void update(int x, int l, int r, int lt, int rt)
{
    if (l>=rt || r<=lt)
        return;
    propagate(x, l, r);
    if (l>=lt && r<=rt)
    {
        swap(ones[x], zeros[x]);
        lazy[x]=(lazy[x]+1)%2;
        return;
    }
    update(2*x+1, l, (l+r)/2, lt, rt);
    update(2*x+2, (l+r)/2, r, lt, rt);
    ones[x]=(ones[2*x+1]+ones[2*x+2])%MOD;
    zeros[x]=(zeros[2*x+1]+zeros[2*x+2])%MOD;

    return;
}

void buildtree(int x, int l, int r)
{
    if (r-l==1)
    {
        if (l>=m)
        {
            ones[x]=0;
            zeros[x]=0;
            return;
        }
        if (a[l]==1)
        {
            ones[x]=factor[l+n];
            zeros[x]=0;
        }
        else
        {
            ones[x]=0;
            zeros[x]=factor[l+n];
        }
        return;
    }
    buildtree(2*x+1, l, (l+r)/2);
    buildtree(2*x+2, (l+r)/2, r);
    ones[x]=(ones[2*x+1]+ones[2*x+2])%MOD;
    zeros[x]=(zeros[2*x+1]+zeros[2*x+2])%MOD;

    return;
}

void init(int N, int M, vector<int> P, vector<int> A)
{
    n=N;
    m=M;
    parent=P;
    a=A;
    for (int i=1; i<n+m; i++)
        adj[parent[i]].push_back(i);
    calcsize(0);
    calcfactor(0, 1);
    buildtree(0, 0, MAXN);
    //for (int i=0; i<n+m; i++)
      //  cout << factor[i] << ' ';
    //cout << '\n';
    //cout << "root " << ones[0] << ' ' << zeros[0] << '\n';
    //for (int i=0; i<m; i++)
      //  cout << zeros[i+MAXN-1] << ' ' << ones[i+MAXN-1] << '\n';

    return;
}

int count_ways(int l, int r)
{
    l=l-n;
    r=r-n;
    update(0, 0, MAXN, l, r+1);
    //long long total=(ones[0]+MOD-zeros[0])%MOD;
    long long total=ones[0];

    return total;
}

Subtask #1
0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Runtime error	1440 ms	2097152 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Runtime error	344 KB	Execution killed with signal 11
3	Halted	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Runtime error	1440 ms	2097152 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	6 ms	2772 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	6 ms	2772 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Runtime error	344 KB	Execution killed with signal 11
3	Halted	0 KB	-

Subtask #7
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Runtime error	1440 ms	2097152 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Runtime error	1440 ms	2097152 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Submission #1057345

Compilation message