Submission #39824

#	Time	Username	Problem	Language	Result	Execution time	Memory
39824		cheater2k	Board (CEOI13_board)	C++14	100 / 100	12 ms	2400 KiB

board

#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 (stderr)

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 / 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