Submission #777274

#	Time	Username	Problem	Language	Result	Execution time	Memory
777274		NK_	Board (CEOI13_board)	C++17	100 / 100	109 ms	3924 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] == 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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10