oj.uz

Submission #643494

# Submission time Handle Problem Language Result Execution time Memory
643494 2022-09-22T07:18:54 Z Vanilla Digital Circuit (IOI22_circuit) C++17
16 / 100
 1041 ms 4172 KB 
#include <bits/stdc++.h>
#include "circuit.h"
typedef long long int64;
using namespace std;
const int64 mod = 1000002022;
const int maxn = 2e5 + 2;
// vector <int> ad [maxn];
int64 dp[4 * maxn][2];
int64 lazy[4 * maxn];
int n,m;

void build (int x) {
  if (x >= n) return;
  int l = x * 2 + 1, r = x * 2 + 2;
  build(l); build(r);
  dp[x][0] = ((dp[l][0] * dp[r][0] * 2 % mod) + (dp[l][0] * dp[r][1] % mod) + (dp[l][1] * dp[r][0] % mod)) % mod;
  dp[x][1] = ((dp[l][1] * dp[r][1] * 2 % mod) + (dp[l][0] * dp[r][1] % mod) + (dp[l][1] * dp[r][0] % mod)) % mod;
}
 
void init(int N, int M, vector<int> P, vector<int> A) {
  n = N, m = M;
  for (int i = 0; i < M; i++){
    dp[N+i][A[i]] = 1;
  }
  build(0);
}

void push (int x, int nl, int nr) {
  if (!lazy[x]) return;
  swap(dp[nl][0], dp[nl][1]);
  swap(dp[nr][0], dp[nr][1]);
  lazy[nl] = !lazy[nl];
  lazy[nr] = !lazy[nr];
  lazy[x] = 0;
}


void upd (int x, int l, int r, int il, int ir) {
  // cout << x << " " << l << " " << r << " " << il << " " << ir << "\n";
  int nl = x * 2 + 1, nr = x * 2 + 2;
  if (il <= l && r <= ir) {
    lazy[x] = !lazy[x];
    swap(dp[x][0], dp[x][1]);
    return;
  }
  if (l > ir || r < il) return;
  int mid = (l + r) / 2;
  push(x, nl, nr);
  upd(nl, l, mid, il, ir); upd(nr, mid + 1, r, il, ir);
  dp[x][0] = ((dp[nl][0] * dp[nr][0] * 2 % mod) + (dp[nl][0] * dp[nr][1] % mod) + (dp[nl][1] * dp[nr][0] % mod)) % mod;
  dp[x][1] = ((dp[nl][1] * dp[nr][1] * 2 % mod) + (dp[nl][0] * dp[nr][1] % mod) + (dp[nl][1] * dp[nr][0] % mod)) % mod;
}

int count_ways(int L, int R) {
  // for (int i = L; i <= R; i++){
  //   swap(dp[i][0], dp[i][1]);
  // }
  upd(0, n, n + m - 1, L, R);
  return dp[0][1];
}

Subtask #1
0 / 2.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 2112 KB Output is correct
2 Correct 823 ms 3880 KB Output is correct
3 Correct 1041 ms 3880 KB Output is correct
4 Correct 928 ms 3988 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 2112 KB Output is correct
2 Correct 823 ms 3880 KB Output is correct
3 Correct 1041 ms 3880 KB Output is correct
4 Correct 928 ms 3988 KB Output is correct
5 Correct 680 ms 2248 KB Output is correct
6 Correct 841 ms 4168 KB Output is correct
7 Correct 973 ms 4172 KB Output is correct
8 Correct 840 ms 3912 KB Output is correct
9 Correct 500 ms 336 KB Output is correct
10 Correct 822 ms 556 KB Output is correct
11 Correct 1031 ms 592 KB Output is correct
12 Correct 717 ms 464 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 336 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 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 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 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -