oj.uz

답안 #39822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39822 2018-01-20T03:04:32 Z cheater2k 게임판 (CEOI13_board) C++14
0 / 100
 11 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 (!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:82: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
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

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 Incorrect 3 ms 2160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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