Submission #1248517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248517		kaiboy	Board (CEOI13_board)	C++20	40 / 100	40 ms	3144 KiB

board

#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int   N = 100000;
const int   M = 100000;
const int  N_ = 1 << 17;
const int INF = 0x3f3f3f3f;

char aa[N + 1], bb[M + 1];
int st0[N_ << 1], st1[N_ << 1], lz[N_], h_, n_;

void put(int i) {
	swap(st0[i], st1[i]);
	if (i < n_)
		lz[i] ^= 1;
}

void pus(int i) {
	if (lz[i]) {
		int l = i << 1, r = l ^ 1;
		put(l), put(r), lz[i] = 0;
	}
}

void pul(int i) {
	if (!lz[i]) {
		int l = i << 1, r = l ^ 1;
		st0[i] = st0[r] != -1 ? st0[r] : st0[l];
		st1[i] = st1[r] != -1 ? st1[r] : st1[l];
	}
}

void push(int i) {
	for (int h = h_; h; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i >>= 1)
		pul(i);
}

void build(int n) {
	h_ = 0, n_ = 1;
	while (n_ <= n)
		h_++, n_ <<= 1;
	for (int i = 0; i < n_; i++)
		st0[i + n_] = i, st1[i + n_] = -1, lz[i] = 0;
	for (int i = n_ - 1; i; i--)
		pul(i);
}

void update(int l, int r) {
	int l_ = l += n_, r_ = r += n_;
	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			put(l++);
		if (!(r & 1))
			put(r--);
	}
	pull(l_), pull(r_);
}

int search0(int r) {
	int l = n_; push(r += n_);
	for ( ; l <= r; l >>= 1, r >>= 1)
		if (!(r & 1)) {
			if (st0[r] != -1)
				return st0[r];
			r--;
		}
	return -1;
}

int search1(int r) {
	int l = n_; push(r += n_);
	for ( ; l <= r; l >>= 1, r >>= 1)
		if (!(r & 1)) {
			if (st1[r] != -1)
				return st1[r];
			r--;
		}
	return -1;
}

int query(int i) {
	push(i += n_);
	return st0[i] == -1;
}

int transform(char *aa, int n) {
	int m = 0;
	build(n);
	for (int i = 0; i < n; i++) {
		char a = aa[i];
		if (a == '1')
			m++;
		else if (a == '2')
			update(m, m), m++;
		else if (a == 'U') {
			if (query(m - 1))
				update(m - 1, m - 1);
			m--;
		} else if (a == 'L')
			update(search1(m - 1), m - 1);
		else
			update(search0(m - 1), m - 1);
	}
	for (int h = 0; h < m; h++)
		aa[h] = query(h);
	return m;
}

int main() {
	cin >> aa >> bb;
	int n = strlen(aa), m = strlen(bb);
	n = transform(aa, n);
	m = transform(bb, m);
	if (n > m)
		swap(n, m), swap(aa, bb);
	int ans = INF, i_ = 0;
	while (i_ < n && aa[i_] == bb[i_])
		i_++;
	for (int d = 0, i = i_; i <= n && i < i_ + 19; i++) {
		ans = min(ans, n - i + abs(d) + m - i);
		if (i < n)
			d = d * 2 + aa[i] - bb[i];
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 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