oj.uz

Submission #971037

# Submission time Handle Problem Language Result Execution time Memory
971037 2024-04-27T21:05:13 Z ALeonidou Digital Circuit (IOI22_circuit) C++17
4 / 100
 554 ms 2756 KB 
#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;
}

ll n,m;
vi p,a;
ll dif;
ll ans;
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);
}

int count_ways(int L, int R) {
    //subtask 4: L = R
    ll l = L-n;
    if (a[l] == 1){
        a[l] = 0;
        ans = (ans - dif + MOD) % MOD;
    }
    else{
        a[l] = 1;
        ans = (ans + dif) % MOD;
    }
    return ans;
}

/*

3 4 4
-1 0 0 1 1 2 2
1 1 1 1
4 4
4 4
5 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 Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 1596 KB Output is correct
2 Correct 535 ms 2756 KB Output is correct
3 Correct 513 ms 2748 KB Output is correct
4 Correct 554 ms 2756 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 1596 KB Output is correct
2 Correct 535 ms 2756 KB Output is correct
3 Correct 513 ms 2748 KB Output is correct
4 Correct 554 ms 2756 KB Output is correct
5 Incorrect 407 ms 1368 KB 1st lines differ - on the 1st token, expected: '105182172', found: '2777846'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -