oj.uz

Submission #650801

# Submission time Handle Problem Language Result Execution time Memory
650801 2022-10-15T11:43:38 Z ShirleyM Digital Circuit (IOI22_circuit) C++17
16 / 100
 1051 ms 18252 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(a) a.begin(),a.end()

const int mod = 1000002022;

int n,m;
vvi adj;
vi a;
//vi cnt_st, cnt_h;
vi mul;

struct seg{
    int l,r,mid;
    int cnt0=0, cnt1=0;
    seg *lp, *rp;
    bool flag=0;

    void init(int l_, int r_){
        l=l_; r=r_;
        mid = (l+r)/2;
        if(l+1 < r){
            lp = new seg();
            rp = new seg();
            lp->init(l,mid);
            rp->init(mid,r);
        }
    }

    void set(){
        int tmp = cnt0;
        cnt0 = cnt1;
        cnt1 = tmp;
        flag=!flag;
    }

    void push(){
        if(flag){
            lp->set();
            rp->set();
            flag=0;
        }
    }

    void pull(){
        cnt1 = ((lp->cnt0 * rp->cnt1)%mod + (lp->cnt1 * rp->cnt0)%mod + (2*lp->cnt1*rp->cnt1)%mod)%mod;
        cnt0 = ((lp->cnt0 * rp->cnt1)%mod + (lp->cnt1 * rp->cnt0)%mod + (2*lp->cnt0*rp->cnt0)%mod)%mod;
    }

    void update_swap(int a, int b){
        if(a<=l && r<=b){
            set();
            return;
        }
        if(l>=b || r<=a) return;
        push();
        lp->update_swap(a,b);
        rp->update_swap(a,b);
        pull();
    }

    void update(int ind, int val){
        if(l==r-1){
            if(val){
                cnt1=1; cnt0=0;
            }
            else{
                cnt0=1; cnt1=0;
            }
            return;
        }
        if(ind<mid) lp->update(ind,val);
        else rp->update(ind,val);
        pull();
    }

    int query(){
        return cnt1;
    }
};

seg sg;

void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
    n=N;m=M;
    adj.resize(n+m);
    loop(i,1,n+m){
        adj[P[i]].pb(i);
    }
    a.resize(n+m);
    sg.init(0,m);
    loop(i,0,m){
        sg.update(i,A[i]);
        a[i+n] = A[i];
    }
}

int32_t count_ways(int32_t L, int32_t R) {
    int l=L, r=R;
    l-=n; r-=n;
    sg.update_swap(l,r+1);
    return sg.query();

}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 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 Incorrect 1 ms 464 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 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 1 ms 464 KB 1st lines differ - on the 1st token, expected: '509', found: '131006524'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 9284 KB Output is correct
2 Correct 853 ms 18232 KB Output is correct
3 Correct 1006 ms 18164 KB Output is correct
4 Correct 885 ms 18252 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 9284 KB Output is correct
2 Correct 853 ms 18232 KB Output is correct
3 Correct 1006 ms 18164 KB Output is correct
4 Correct 885 ms 18252 KB Output is correct
5 Correct 605 ms 9272 KB Output is correct
6 Correct 982 ms 18200 KB Output is correct
7 Correct 1035 ms 18224 KB Output is correct
8 Correct 967 ms 18224 KB Output is correct
9 Correct 534 ms 848 KB Output is correct
10 Correct 1051 ms 1360 KB Output is correct
11 Correct 760 ms 1360 KB Output is correct
12 Correct 826 ms 1360 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 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 Incorrect 1 ms 464 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 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 1 ms 464 KB 1st lines differ - on the 1st token, expected: '509', found: '131006524'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

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