답안 #39823 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39823	2018-01-20T03:07:38 Z	cheater2k	게임판 (CEOI13_board)	C++14	20 / 100	14 ms	2400 KB

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;
	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;
		if (dist > 1) {
			cout << ans + 2 * (pathA.size() - 1 - i) + dist << endl;
			return 0;
		}	
	}
	cout << dist + 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:83: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

#	결과	메모리	Grader output
1	Correct	2024 KB	Output is correct
2	Correct	2024 KB	Output is correct
3	Correct	2024 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2400 KB	Output is correct
2	Correct	2 ms	2160 KB	Output is correct
3	Incorrect	5 ms	2340 KB	Output isn't correct

Subtask #3
0 / 10.0

#	결과	메모리	Grader output
1	Correct	2024 KB	Output is correct
2	Incorrect	2024 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2176 KB	Output is correct
2	Incorrect	14 ms	2340 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	2024 KB	Output is correct
2	Correct	2024 KB	Output is correct
3	Correct	2024 KB	Output is correct
4	Correct	2024 KB	Output is correct
5	Correct	2024 KB	Output is correct

Subtask #6
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2024 KB	Output is correct
2	Incorrect	1 ms	2024 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2160 KB	Output is correct
2	Incorrect	12 ms	2340 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	2340 KB	Output is correct
2	Incorrect	7 ms	2340 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	2340 KB	Output is correct
2	Incorrect	11 ms	2340 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	11 ms	2340 KB	Output isn't correct
2	Halted	0 ms	0 KB	-