oj.uz

Submission #912720

# Submission time Handle Problem Language Result Execution time Memory
912720 2024-01-19T18:47:10 Z biank Digital Circuit (IOI22_circuit) C++17
16 / 100
 605 ms 3280 KB 
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll; 
#define ALL(x) x.begin(),x.end()
#define SIZE(x) (int)x.size()
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define fst first
#define snd second
#define pb push_back
const int MAXN = 2e5;
const int MOD = 1e9+2022;
vi s;
int n, m;
int dp[MAXN][2];
 
int mul(int x, int y) {
    return int(1LL*x*y%MOD);
}

void add(int &x, int y) {
    x+=y;
    if(x>=MOD) x-=MOD;
}
 
void compute_dp(int u) {
    int l=2*u+1, r=2*u+2;
    
    int aux = mul(dp[l][0], dp[r][1]);
    add(aux, mul(dp[l][1], dp[r][0]));
    dp[u][1] = dp[u][0] = aux;
    
    aux = mul(mul(2, dp[l][0]), dp[r][0]);
    add(dp[u][0], aux);
    
    aux = mul(mul(2, dp[l][1]), dp[r][1]);
    add(dp[u][1], aux);
}
 
void dfs(int u) {
    if(u>=n) {
        dp[u][s[u-n]] = 1;
        dp[u][!s[u-n]] = 0;
        return;
    }
    dfs(2*u+1), dfs(2*u+2);
    compute_dp(u);
}
 
void init(int N, int M, vi /*P*/, vi A) {
    s=A, n=N, m=M;
    dfs(0);
}

bool lazy[MAXN];

void pass(int u) {
    if(!lazy[u]) return;
    if(2*u+2<MAXN) {
        lazy[2*u+1] ^= 1;
        lazy[2*u+2] ^= 1;
    }
    swap(dp[u][0], dp[u][1]);
    lazy[u] = false;
}

void update(int ql, int qr, int nl, int nr, int u) {
    pass(u);
    if(qr <= nl || nr <= ql) {
        return;
    }
    if(ql <= nl && nr <= qr) {
        lazy[u] ^= 1;
        pass(u);
        return;
    }
    int nm=(nl+nr)/2;
    update(ql,qr,nl,nm,2*u+1);
    update(ql,qr,nm,nr,2*u+2);
    compute_dp(u);
}
 
int count_ways(int L, int R) {
    update(L-n, R-n+1, 0, m, 0);
    return dp[0][1];
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
3 Halted 0 ms 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 1 ms 340 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '706880838', found: '771166560'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 1880 KB Output is correct
2 Correct 538 ms 3276 KB Output is correct
3 Correct 524 ms 3272 KB Output is correct
4 Correct 509 ms 3276 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 1880 KB Output is correct
2 Correct 538 ms 3276 KB Output is correct
3 Correct 524 ms 3272 KB Output is correct
4 Correct 509 ms 3276 KB Output is correct
5 Correct 443 ms 1864 KB Output is correct
6 Correct 605 ms 3280 KB Output is correct
7 Correct 572 ms 3280 KB Output is correct
8 Correct 560 ms 3276 KB Output is correct
9 Correct 239 ms 344 KB Output is correct
10 Correct 529 ms 856 KB Output is correct
11 Correct 521 ms 612 KB Output is correct
12 Correct 518 ms 616 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 1 ms 340 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '706880838', found: '771166560'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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