oj.uz

Submission #986791

# Submission time Handle Problem Language Result Execution time Memory
986791 2024-05-21T08:35:10 Z cig32 Lamps (JOI19_lamps) C++17
4 / 100
 26 ms 27720 KB 
#include "bits/stdc++.h"
#define int long long
using namespace std;
mt19937_64 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  return uniform_int_distribution<int>(x, y)(rng);
}
const int MAXN = 1e6 + 10;
string a, b;
int n;
int ps[MAXN];
int dpf(int l, int r, int tog) {
  while(l <= r && (a[l] ^ tog) == b[l]) l++;
  while(l <= r && (a[r] ^ tog) == b[r]) r--;
  if(l > r) return 0;
  int nums = ps[r] - ps[l];
  int cnt0, cnt1;
  if(nums % 2 == 1) {
    cnt0 = cnt1 = (nums + 1) / 2;
  }
  else {
    cnt0 = nums / 2 + 1, cnt1 = nums / 2;
    if(b[l] == '1') swap(cnt0, cnt1);
  }
  //cout << l << " " << r << " " << cnt0 << " " << cnt1 << "\n";
  // set, then bruhopen
  int ans = 1 + min(cnt0, cnt1);
  ans = min(ans, 1 + dpf(l, r, tog ^ 1));
  return ans;
}
void solve(int tc) {
  cin >> n;
  cin >> a >> b;
  a = " " + a;
  b = " " + b;
  for(int i=2; i<=n; i++) ps[i] = ps[i-1] + (b[i] != b[i-1]);
  cout << dpf(1, n, 0) << '\n';
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
/*
g++ T2421.cpp -std=c++17 -O2 -o T2421
./T2421 < input.txt
*/

Subtask #1
0 / 6.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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 12076 KB Output is correct
8 Correct 25 ms 27640 KB Output is correct
9 Correct 26 ms 27656 KB Output is correct
10 Correct 25 ms 27652 KB Output is correct
11 Correct 25 ms 27720 KB Output is correct
12 Correct 10 ms 12036 KB Output is correct
13 Correct 10 ms 12036 KB Output is correct
14 Correct 10 ms 12548 KB Output is correct

Subtask #4
0 / 49.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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -