oj.uz

Submission #826244

# Submission time Handle Problem Language Result Execution time Memory
826244 2023-08-15T11:30:02 Z alvingogo Digital Circuit (IOI22_circuit) C++17
52 / 100
 836 ms 26908 KB 
#include "circuit.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;

const int mod=1000002022;
void add(int& x,int y){
    x+=y;
    x-=mod*(x>=mod);
}
int mul(int x,int y){
    return 1ll*x*y%mod;
}
int po(int x,int y){
    int z=1;
    while(y){
        if(y&1){
            z=mul(z,x);
        }
        x=mul(x,x);
        y>>=1;
    }
    return z;
}
const int mod2=2242157;
int inv(int x){
    return x==1?1:(int)(1ll*(mod2-mod2/x)*inv(mod2%x)%mod2);
}
vector<int> g,a;
struct ST{
    struct no{
        int sum=0,ans=0,tag=0;
    };
    vector<no> st;
    void init(int x){
        st.resize(4*x);
    }
    void upd(int v){
        st[v].ans=(st[v].sum-st[v].ans+mod)%mod;
        st[v].tag^=1;
    }
    void pudo(int v){
        if(st[v].tag){
            upd(2*v+1);
            upd(2*v+2);
            st[v].tag=0;
        }
    }
    void pull(int v){
        st[v].ans=(st[2*v+1].ans+st[2*v+2].ans)%mod;
    }
    void build(int v,int L,int R){
        if(L==R){
            st[v].sum=g[L];
            st[v].ans=st[v].sum*a[L];
            return;
        }
        int m=(L+R)/2;
        build(2*v+1,L,m);
        build(2*v+2,m+1,R);
        pull(v);
        st[v].sum=(st[2*v+1].sum+st[2*v+2].sum)%mod;
    }
    void toggle(int v,int L,int R,int l,int r){
        if(L==l && r==R){
            upd(v);
            return;
        }
        pudo(v);
        int m=(L+R)/2;
        if(r<=m){
            toggle(2*v+1,L,m,l,r);
        }
        else if(l>m){
            toggle(2*v+2,m+1,R,l,r);
        }
        else{
            toggle(2*v+1,L,m,l,m);
            toggle(2*v+2,m+1,R,m+1,r);
        }
        pull(v);
    }
    int query(){
        return st[0].ans; 
    }
}st;

const int x[2]={2,223};
int cnt[2]={0};
int pe=1;
int n,m;
struct tn{
    vector<int> ch;
    int deg=0;
    int cs[2]={0};
    int dx=0;
};
vector<tn> v;
void dfs(int r,int a,int b,int c){
    if(r>=n){
        int z=1ll*pe*inv(c)%mod2;
        z=mul(z,po(2,cnt[0]-a));
        z=mul(z,po(223,cnt[1]-b));
        g[r-n]=z;
        return;
    }
    for(auto h:v[r].ch){
        dfs(h,a+v[r].cs[0],b+v[r].cs[1],1ll*c*v[r].dx%mod2);
    }
}
void init(int N, int M, vector<int> p, vector<int> A) {
    n=N;
    m=M;
    a=A;
    st.init(m);
    g.resize(m);
    v.resize(n+m);
    for(int i=1;i<n+m;i++){
        v[p[i]].ch.push_back(i);
        v[p[i]].deg++;
    }
    for(int i=0;i<n;i++){
        int s=v[i].deg;
        while(s%2==0){
            s/=2;
            v[i].cs[0]++;
            cnt[0]++;
        }
        while(s%223==0){
            s/=223;
            v[i].cs[1]++;
            cnt[1]++;
        }
        v[i].dx=s;
        pe=1ll*pe*s%mod2;
    }
    dfs(0,0,0,1);
    st.build(0,0,m-1);
}

int count_ways(int L, int R) {
    st.toggle(0,0,m-1,L-n,R-n);
    return st.query();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 432 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Incorrect 1 ms 384 KB 1st lines differ - on the 1st token, expected: '759476520', found: '844678486'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 6460 KB Output is correct
2 Correct 693 ms 12576 KB Output is correct
3 Correct 647 ms 12624 KB Output is correct
4 Correct 691 ms 12588 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 6460 KB Output is correct
2 Correct 693 ms 12576 KB Output is correct
3 Correct 647 ms 12624 KB Output is correct
4 Correct 691 ms 12588 KB Output is correct
5 Correct 593 ms 6468 KB Output is correct
6 Correct 635 ms 12544 KB Output is correct
7 Correct 673 ms 12572 KB Output is correct
8 Correct 584 ms 12560 KB Output is correct
9 Correct 244 ms 592 KB Output is correct
10 Correct 635 ms 1096 KB Output is correct
11 Correct 764 ms 1060 KB Output is correct
12 Correct 791 ms 1064 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 397 ms 6460 KB Output is correct
14 Correct 693 ms 12576 KB Output is correct
15 Correct 647 ms 12624 KB Output is correct
16 Correct 691 ms 12588 KB Output is correct
17 Correct 593 ms 6468 KB Output is correct
18 Correct 635 ms 12544 KB Output is correct
19 Correct 673 ms 12572 KB Output is correct
20 Correct 584 ms 12560 KB Output is correct
21 Correct 244 ms 592 KB Output is correct
22 Correct 635 ms 1096 KB Output is correct
23 Correct 764 ms 1060 KB Output is correct
24 Correct 791 ms 1064 KB Output is correct
25 Correct 651 ms 18632 KB Output is correct
26 Correct 795 ms 19088 KB Output is correct
27 Correct 774 ms 19012 KB Output is correct
28 Correct 653 ms 19000 KB Output is correct
29 Correct 819 ms 26908 KB Output is correct
30 Correct 836 ms 26900 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 432 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Incorrect 1 ms 384 KB 1st lines differ - on the 1st token, expected: '759476520', found: '844678486'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 432 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Incorrect 1 ms 384 KB 1st lines differ - on the 1st token, expected: '759476520', found: '844678486'
22 Halted 0 ms 0 KB -