Submission #105169

#	Time	Username	Problem	Language	Result	Execution time	Memory
105169		Noam527	Board (CEOI13_board)	C++17	100 / 100	5 ms	1468 KiB

board

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

vector<int> transform(const string &s) {
	vector<int> val;
	for (const auto &i : s) {
		if (i == '1' || i == '2') val.push_back(i - '1');
		else if (i == 'L') val.back()--;
		else if (i == 'R') val.back()++;
		else {
			if (val.size() == 1) {
				val.pop_back();
				continue;
			}
			int x = val.back();
			val.pop_back();
			if (x >= 0) val.back() += x / 2;
			else {
				x = -x;
				val.back() -= (x + 1) / 2;
			}
		}
	}
	for (int i = (int)val.size() - 1; i > 0; i--) {
		if (val[i] >= 0) {
			val[i - 1] += val[i] / 2;
			val[i] %= 2;
		}
		else {
			val[i] = -val[i];
			val[i - 1] -= (val[i] + 1) / 2;
			val[i] %= 2;
		}
	}
	return val;
}

string s, t;
vector<int> a, b;
int ans = md;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> s >> t;
	a = transform(s);
	b = transform(t);
	if (OO) {
		cout << "a: ";
		for (const auto &i : a) cout << i << " "; cout << '\n';
		cout << "b: ";
		for (const auto &i : b) cout << i << " "; cout << '\n';
	}
	int off = 0;
	while (a.size() > b.size()) {
		off++;
		a.pop_back();
	}
	while (a.size() < b.size()) {
		off++;
		b.pop_back();
	}
	int dist = 0, n = a.size();
	if (n != 0) {
		if (a > b) swap(a, b);
	}
	ans = min(ans, off + 2 * n);
	for (int i = 0; i < n; i++) {
		if (dist > 10 * n) break;
		dist = 2 * dist + 1;
		if (a[i] == 1) dist--;
		if (b[i] == 0) dist--;
		ans = min(ans, off + dist + 2 * (n - 1 - i));
	}
	finish(ans);
}

Compilation message (stderr)

board.cpp: In function 'int main()':
board.cpp:57:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : a) cout << i << " "; cout << '\n';
   ^~~
board.cpp:57:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : a) cout << i << " "; cout << '\n';
                                             ^~~~
board.cpp:59:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : b) cout << i << " "; cout << '\n';
   ^~~
board.cpp:59:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : b) cout << i << " "; cout << '\n';
                                             ^~~~

• 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