oj.uz

Submission #777277

# Submission time Handle Problem Language Result Execution time Memory
777277 2023-07-09T01:31:42 Z NK_ Board (CEOI13_board) C++17
100 / 100
 102 ms 3796 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())

using str = string;
using ll = long long;

template<class T> using V = vector<T>;

const int INF = int(1e9) + 10;
const int DIF = 10;

using T = array<int, 2>;

const int nax = (1 << 17);

T seg[2 * nax];
int lazy[2 * nax];

void push(int x, int L, int R) {
	lazy[x] %= 2;
	if (lazy[x] == 1) swap(seg[x][0], seg[x][1]);
	if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] += lazy[x];
	lazy[x] = 0;
}

void pull(int x) { seg[x] = T{seg[2*x][0] + seg[2*x+1][0], seg[2*x][1] + seg[2*x+1][1]};  }

void flip(int l, int r, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (r < L || R < l) return;
	if (l <= L && R <= r) {
		lazy[x]++; push(x, L, R); return;
	}

	int M = (L + R) / 2;
	flip(l, r, 2*x, L, M);
	flip(l, r, 2*x+1, M+1, R);
	pull(x);
}

void upd(int p, T v, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (p < L || R < p) return;
	if (L == R) { 
		seg[x] = v; return; 
	}

	int M = (L + R) / 2;
	upd(p, v, 2*x, L, M);
	upd(p, v, 2*x+1, M+1, R);
	pull(x);
}

int find_last(int p, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); 
	if (seg[x][p] == 0) return nax;
	if (L == R) return L;

	int M = (L + R) / 2;
	int res = find_last(p, 2*x+1, M+1, R);
	if (res != nax) return res;
	return find_last(p, 2*x, L, M);
}

int value(int p, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (L == R) { return seg[x][0] == 0; }

	int M = (L + R) / 2;
	if (p <= M) return value(p, 2*x, L, M);
	else return value(p, 2*x+1, M+1, R);
}

const T ONE = {0, 1}, ZER = {1, 0}, EMP = {0, 0};

int main() {
	cin.tie(0)->sync_with_stdio(0);

	for(int i = 0; i < 2 * nax; i++) {
		lazy[i] = 0;
		seg[i] = EMP;
	}

	str A, B; cin >> A >> B;

	int d = -1;
	auto add = [&](bool pos) {
		int c = (pos ? 0 : 1);
		int p = find_last(c);
		flip(p, d - 1);
	};

	auto get = [&](str& S) {
		d = 0;
		for(auto& c : S) {
			if (isdigit(c)) upd(d++, c == '2' ? ONE : ZER);
			if (c == 'U') upd(--d, EMP);
			if (c == 'L') add(0);
			if (c == 'R') add(1);
		}

		S = "0";
		for(int i = 0; i < d; i++) {
			S += char('0' + value(i));
			upd(i, EMP);
		}
	};

	get(A), get(B);

	int ans = INF;
	int xa = 0, xb = 0; bool aft = 0;
	for(int i = 0; i < min(sz(A), sz(B)); i++) {
		if (abs(xa - xb) > DIF) break;
		if (A[i] != B[i]) aft = 1;

		if (aft) {
			xa = (2 * xa) + (A[i] - '0');
			xb = (2 * xb) + (B[i] - '0');
		}

		int upa = sz(A) - i - 1, upb = sz(B) - i - 1; 
		ans = min(ans, upa + upb + abs(xa - xb));
	}

	cout << ans << nl;

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3284 KB Output is correct
2 Correct 2 ms 3284 KB Output is correct
3 Correct 1 ms 3284 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3620 KB Output is correct
2 Correct 11 ms 3448 KB Output is correct
3 Correct 38 ms 3624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3284 KB Output is correct
2 Correct 2 ms 3284 KB Output is correct
3 Correct 2 ms 3284 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3412 KB Output is correct
2 Correct 56 ms 3668 KB Output is correct
3 Correct 28 ms 3588 KB Output is correct
4 Correct 1 ms 3284 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3284 KB Output is correct
2 Correct 2 ms 3284 KB Output is correct
3 Correct 2 ms 3284 KB Output is correct
4 Correct 2 ms 3284 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3412 KB Output is correct
2 Correct 6 ms 3412 KB Output is correct
3 Correct 2 ms 3284 KB Output is correct
4 Correct 2 ms 3284 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3412 KB Output is correct
2 Correct 50 ms 3668 KB Output is correct
3 Correct 28 ms 3540 KB Output is correct
4 Correct 2 ms 3284 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3796 KB Output is correct
2 Correct 97 ms 3688 KB Output is correct
3 Correct 10 ms 3412 KB Output is correct
4 Correct 11 ms 3436 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3668 KB Output is correct
2 Correct 100 ms 3796 KB Output is correct
3 Correct 8 ms 3412 KB Output is correct
4 Correct 8 ms 3424 KB Output is correct
5 Correct 90 ms 3712 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3668 KB Output is correct
2 Correct 96 ms 3668 KB Output is correct
3 Correct 67 ms 3604 KB Output is correct
4 Correct 13 ms 3412 KB Output is correct
5 Correct 13 ms 3452 KB Output is correct
6 Correct 95 ms 3668 KB Output is correct