Submission #971068

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
971068	2024-04-27T22:02:53 Z	ALeonidou	Digital Circuit (IOI22_circuit)	C++17	16 / 100	616 ms	8900 KB

circuit

#include "circuit.h"
#include <vector>
#include <iostream>
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define sz(x) (ll)x.size()
#define endl "\n"

typedef vector <int> vi;
typedef pair <ll, ll> ii;
typedef vector <ii> vii;

#define MOD 1000002022
  
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
    for (ll i =0; i<sz(v); i++){
      cout<<v[i]<<" ";
    }
    cout<<endl;
}

ll mpow(ll a, ll b){
    if (b == 0) return 1;
    if (b % 2) return (a * (mpow((a*a)%MOD, b/2)% MOD)) % MOD;
    return mpow((a*a)%MOD, b/2)%MOD;
}

#define MID ((l+r)/2)

ll n,m;
vi p,a;
ll dif, ans;

struct node{    //sum seg tree with lazy (base = input gates => base size = m)
    node *L, *R;
    ll val;
    ll lazy;    //0 or 1 => 1 means toggled

    void build (ll l = 0, ll r=m-1){
        lazy = 0;
        if (l == r){
            val = a[l];
        }
        else{
            L = new node, R =new node;
            L->build(l, MID), R->build(MID+1,r);
            val = L->val + R->val;
        }
    }

    ll query(ll tl, ll tr, ll l = 0, ll r =m-1){
        if (tl <= l && r <= tr){
            return val;
        }   
        else if (r < tl || l > tr){
            return 0;
        }
        else{
            propagate(l,r);
            return L->query(tl,tr,l,MID) + R->query(tl,tr,MID+1,r);
        }
    }   

    void update(ll tl, ll tr, ll l = 0, ll r =m-1){
        if (tl <= l && r <= tr){
            ll siz = r-l+1;
            val = siz - val; //all toggled
            lazy = !lazy;
        }    
        else if (r < tl || l > tr){
            return;
        }
        else{
            propagate(l,r);
            L->update(tl,tr,l,MID);
            R->update(tl,tr,MID+1,r);
            val = L->val + R->val;
        }
    }

    void propagate(ll l, ll r){
        if (lazy){
            ll sizL = MID-l+1;
            ll sizR = r-(MID+1)+1;

            L->val = sizL - (L->val);
            R->val = sizR - (R->val);

            L->lazy = !(L->lazy);
            R->lazy = !(R->lazy);
            lazy = 0;
        }
    }
};

node root;
void init(int N, int M, vector <int> P, vector<int> A) {
    n= N, m = M;
    p = P;
    a = A;
    //subtask 4,5:
    ll treeHeight = 0;
    ll p = m;
    while (p){
        p/=2;
        treeHeight++;
    }
    // dbg(treeHeight);
    dif = 1;
    ll p2 = 1;
    // dbg(m-1-treeHeight);
    for (ll i = 0; i<=m-1-treeHeight; i++){
        dif = (dif + p2) % MOD;
        p2 = (p2 * 2) % MOD;
    }
    // dbg(dif);

    //calc ans:
    ll curOff = 0;
    for (ll i = 0; i<m; i++){
        if (!a[i]) curOff++;
    }
    ll all = mpow(2, n);
    ans = (all - ((dif * curOff) % MOD) + MOD) % MOD;
    // dbg(ans);


    //seg tree for sub 5:
    root.build();
}

int count_ways(int L, int R) {
    //subtask 4: L = R
    ll l = L-n, r = R-n;
    ll prevOn = root.val;
    root.update(l,r);
    ll curOn = root.val;

    ll difVal = (((curOn - prevOn + MOD) % MOD) * dif) % MOD;
    ans = (ans + difVal) % MOD;

    return ans;
}

/*

3 4 4
-1 0 0 1 1 2 2
1 1 1 1
4 4
4 4
4 5
4 4

7 8 1
-1 0 0 1 1 2 2 3 3 4 4 5 5 6 6
1 1 1 1 1 1 1 1
10 10




*/












/*

subtask 1:
    ll l = L-n, r = R-n;
    ll curOn = 0;
    for (ll i =0; i<m; i++){
        if (i >= l && i <= r){
            a[i] = !a[i];
        }
        if (a[i]) curOn++;
    }
*/

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	410 ms	4440 KB	Output is correct
2	Correct	585 ms	8896 KB	Output is correct
3	Correct	555 ms	8888 KB	Output is correct
4	Correct	616 ms	8784 KB	Output is correct

Subtask #5
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	410 ms	4440 KB	Output is correct
2	Correct	585 ms	8896 KB	Output is correct
3	Correct	555 ms	8888 KB	Output is correct
4	Correct	616 ms	8784 KB	Output is correct
5	Correct	521 ms	4440 KB	Output is correct
6	Correct	610 ms	8788 KB	Output is correct
7	Correct	609 ms	8876 KB	Output is correct
8	Correct	580 ms	8900 KB	Output is correct
9	Correct	312 ms	600 KB	Output is correct
10	Correct	562 ms	856 KB	Output is correct
11	Correct	553 ms	856 KB	Output is correct
12	Correct	546 ms	856 KB	Output is correct

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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

Submission #971068

Compilation message