oj.uz

Submission #1097277

# Submission time Handle Problem Language Result Execution time Memory
1097277 2024-10-06T16:02:10 Z codexistent Board (CEOI13_board) C++14
100 / 100
 3 ms 2200 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 3 ms 1624 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1240 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 3 ms 1624 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 2 ms 2140 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 2 ms 2136 KB Output is correct
3 Correct 1 ms 1244 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 2 ms 2200 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 2 ms 2136 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1296 KB Output is correct
6 Correct 2 ms 2200 KB Output is correct