oj.uz

Submission #105169

# Submission time Handle Problem Language Result Execution time Memory
105169 2019-04-10T19:55:17 Z Noam527 Board (CEOI13_board) C++17
100 / 100
 5 ms 1468 KB 
#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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 640 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1404 KB Output is correct
2 Correct 5 ms 1340 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1404 KB Output is correct
2 Correct 5 ms 1404 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 540 KB Output is correct
5 Correct 5 ms 1468 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1404 KB Output is correct
2 Correct 4 ms 1404 KB Output is correct
3 Correct 4 ms 1276 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 528 KB Output is correct
6 Correct 4 ms 1404 KB Output is correct