oj.uz

Submission #39824

# Submission time Handle Problem Language Result Execution time Memory
39824 2018-01-20T03:42:53 Z cheater2k Board (CEOI13_board) C++14
100 / 100
 12 ms 2400 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;

string A, B;
int levelA, levelB;
int ans;

deque<ii> modify(string &S, int &level) {
	deque<ii> st;
	for (int i = 0; i < S.size(); ++i) {
		if (S[i] == '1' || S[i] == '2') {
			int cur = S[i] - '1';
			if (st.empty() || st.back().first != cur) {
				st.push_back(ii(cur, 1));
			} else {
				st.back().second++;
			}
			++level;
		} else if (S[i] == 'L' || S[i] == 'R') {
			int s0 = (S[i] == 'L') ? 0 : 1;
			int s1 = (S[i] == 'L') ? 1 : 0;

			if (st.back().first == s0) {
				int c0 = st.back().second; st.pop_back();
				int c1 = st.back().second; st.pop_back();
				--c1;
				if (c1) {
					st.push_back(ii(s1, c1));
					st.push_back(ii(s0, 1)); 
					st.push_back(ii(s1, c0));
				} else {
					if (st.empty()) st.push_back(ii(s0, 1));
					else st.back().second++;
					st.push_back(ii(s1, c0));
				}
			} else {
				st.back().second--;
				if (st.back().second == 0) st.pop_back();
				
				if (st.empty() || st.back().first != s0) st.push_back(ii(s0, 1));
				else st.back().second++;
			}
		} else { // s[i] == 'U'
			st.back().second--;
			if (st.back().second == 0) st.pop_back();
			--level;
		}
	}
	return st;
}

int main() {
	cin >> A >> B;
	deque<ii> a = modify(A, levelA);
	deque<ii> b = modify(B, levelB);

	if (levelA < levelB) swap(levelA, levelB), a.swap(b);
	// update A to the same level with B
	while(levelA > levelB) {
		--levelA; 
		++ans;
		--a.back().second;
		if (a.back().second == 0) a.pop_back();
	}

	// whether the distance between A and B is 1?
	// if the distance is not equal to 1 -> A and B have to go up to their parents
	vector<bool> pathA, pathB;
	for (auto &i : a) while(i.second-- > 0) pathA.push_back(i.first);
	for (auto &i : b) while(i.second-- > 0) pathB.push_back(i.first);

	// pathA <= pathB
	bool smaller = true;
	for (int i = 0; i < pathA.size(); ++i) {
		if (pathA[i] > pathB[i]) { smaller = false; break; }
		if (pathA[i] < pathB[i]) break;
	}
	if (!smaller) pathA.swap(pathB);

	int dist = 0;
	int mn = pathA.size() * 2 + ans;
	for (int i = 0; i < pathA.size(); ++i) { // pathA.size() = pathB.size()
		dist = 2 * dist + 1;
		if (pathA[i] == 1) --dist;
		if (pathB[i] == 0) --dist;
		mn = min(mn, 2 * ((int)pathA.size() - 1 - i) + dist);

		if (dist > 3) {
			cout << ans + mn << endl;
			return 0;
		}	
	}
	cout << mn + ans << endl;
}

Compilation message

board.cpp: In function 'std::deque<std::pair<int, int> > modify(std::__cxx11::string&, int&)':
board.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); ++i) {
                    ^
board.cpp: In function 'int main()':
board.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pathA.size(); ++i) {
                    ^
board.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pathA.size(); ++i) { // pathA.size() = pathB.size()
                    ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2400 KB Output is correct
2 Correct 2 ms 2160 KB Output is correct
3 Correct 7 ms 2340 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2176 KB Output is correct
2 Correct 12 ms 2340 KB Output is correct
3 Correct 2 ms 2340 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2160 KB Output is correct
2 Correct 9 ms 2340 KB Output is correct
3 Correct 7 ms 2340 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2340 KB Output is correct
2 Correct 6 ms 2340 KB Output is correct
3 Correct 1 ms 2024 KB Output is correct
4 Correct 2 ms 2024 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2340 KB Output is correct
2 Correct 7 ms 2340 KB Output is correct
3 Correct 1 ms 2024 KB Output is correct
4 Correct 1 ms 2024 KB Output is correct
5 Correct 12 ms 2340 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2340 KB Output is correct
2 Correct 7 ms 2340 KB Output is correct
3 Correct 9 ms 2340 KB Output is correct
4 Correct 2 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 10 ms 2340 KB Output is correct