oj.uz

Submission #777274

# Submission time Handle Problem Language Result Execution time Memory
777274 2023-07-09T01:27:27 Z NK_ Board (CEOI13_board) C++17
100 / 100
 109 ms 3924 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);
}

void print(int x = 1, int L = 0, int R = nax - 1) {
	cout << "(" << x << ", " << L << ", " << R << ") => " << lazy[x] << " " << seg[x][0] << " " << seg[x][1] << endl;
	if (L == R) return;
	int M = (L + R) / 2;
	print(2*x, L, M);
	print(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);
		// cout << p << " <-> " << d << " -> " << c << endl;
		assert(p != nax);
		flip(p, d - 1);
	};

	auto get = [&](str& S) {
		d = 0;
		for(auto& c : S) {
			// print();
			// cout << d << " " << c << " -> ";
			// for(int i = 0; i < d; i++) cout << value(i);
			// cout << endl;
			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);
			// print();
		}

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

	get(A);
	get(B);

	int ans = INF;

	// cout << A << " " << B << endl;

	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 40 ms 3628 KB Output is correct
2 Correct 11 ms 3484 KB Output is correct
3 Correct 45 ms 3752 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 1 ms 3284 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3412 KB Output is correct
2 Correct 57 ms 3828 KB Output is correct
3 Correct 29 ms 3668 KB Output is correct
4 Correct 2 ms 3284 KB Output is correct
5 Correct 2 ms 3408 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 3400 KB Output is correct
3 Correct 2 ms 3400 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 6 ms 3424 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 3396 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3500 KB Output is correct
2 Correct 54 ms 3796 KB Output is correct
3 Correct 30 ms 3668 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 99 ms 3796 KB Output is correct
2 Correct 99 ms 3796 KB Output is correct
3 Correct 13 ms 3472 KB Output is correct
4 Correct 10 ms 3460 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 3668 KB Output is correct
2 Correct 109 ms 3924 KB Output is correct
3 Correct 6 ms 3444 KB Output is correct
4 Correct 9 ms 3412 KB Output is correct
5 Correct 93 ms 3796 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 3668 KB Output is correct
2 Correct 102 ms 3876 KB Output is correct
3 Correct 71 ms 3736 KB Output is correct
4 Correct 14 ms 3480 KB Output is correct
5 Correct 17 ms 3480 KB Output is correct
6 Correct 92 ms 3892 KB Output is correct