Submission #1097277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097277		codexistent	Board (CEOI13_board)	C++14	100 / 100	3 ms	2200 KiB

board

#include <bits/stdc++.h>
 
using namespace std;
 
#define D(x) ({ cerr << "| DEBUG #" << __LINE__ << " IN " << __FUNCTION__ << "() \t| \t" << #x << " = " << (x) << endl; void(); })
 
#define endl "\n"
 
constexpr int N = 1e5 + 10;
 
using ll = long long;
 
struct Big {
	int arr[N], tot;
	Big() {
		tot = arr[0] = 1;
	}
	int shift(int &a) {
		int r = 0;
		if (a > 1) {
			r += a >> 1;
			a &= 1;
		}
		else if (a < 0) {
			a = -a;
			r -= (a + 1) >> 1;
			a &= 1;
		}
		return r;
	}
	void LS() {
		arr[tot++] = 0;
	}
	void RS() {
		arr[tot++] = 1;
	}
	void U() {
		--tot;
		arr[tot - 1] += shift(arr[tot]);
	}
	void L() {
		--arr[tot - 1];
	}
	void R() {
		++arr[tot - 1];
	}
	auto to_string() {
		basic_string<int> res;
		for (int i = tot - 1; i; --i) {
			arr[i - 1] += shift(arr[i]);
			res.push_back(arr[i]);
		}
		int t = arr[0];
		while (t) {
			int k = shift(t);
			res.push_back(t);
			t = k;
		}
		while (res.back() == 0) res.pop_back(), exit(1);
		reverse(res.begin(), res.end());
		return res;
	}
};
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	string s1, s2;
	cin >> s1 >> s2;
	Big r1, r2;
	for (char c : s1) {
		if (c == '1') r1.LS();
		if (c == '2') r1.RS();
		if (c == 'U') r1.U();
		if (c == 'L') r1.L();
		if (c == 'R') r1.R();
	}
	for (char c : s2) {
		if (c == '1') r2.LS();
		if (c == '2') r2.RS();
		if (c == 'U') r2.U();
		if (c == 'L') r2.L();
		if (c == 'R') r2.R();
	}
	int ad = 0;
	auto v1 = r1.to_string();
	auto v2 = r2.to_string();
	while (v1.size() > v2.size()) v1.pop_back(), ++ad;
	while (v2.size() > v1.size()) v2.pop_back(), ++ad;
	if (v1 < v2) swap(v1, v2);
	int diff = 0, ans = 2e5;
	int n = v1.size();
	for (int i = 0; i < n; ++i) {
		diff = (diff << 1) + v1[i] - v2[i];
		if (diff > 2e5) break;
		ans = min(ans, diff + (n - i - 1) * 2);
	}
	cout << ans + ad << endl;
	return 0;
}
//testing

• 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