Submission #777260

#	Time	Username	Problem	Language	Result	Execution time	Memory
777260		NK_	Board (CEOI13_board)	C++17	0 / 100	87 ms	7488 KiB

board

// 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]) 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) {
		// cout << L << " " << R << endl;
		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 (L == R) { seg[x] = v; return; }

	int M = (L + R) / 2;
	if (p <= M) upd(p, v, 2*x, L, M);
	else 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;

	set<int> F;

	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) {
			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);

			// for(int i = 0; i < d; i++) cout << value(i);
			// cout << endl;
		}

		S = "";
		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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10