oj.uz

Submission #4549

# Submission time Handle Problem Language Result Execution time Memory
4549 2013-10-27T03:07:58 Z tncks0121 Board (CEOI13_board) C++
100 / 100
 4 ms 2228 KB 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 100005;
char A[N_], B[N_];
int AN, BN;
int P[N_], Q[N_], PN, QN, PD, QD;
stack<int> PS, QS;
ll res, depth;

void convert (char *S, int L, stack<int> &stk, int &depth) {
	for(int i = 1; i <= L; i++) {
		if(S[i] == '1') {
			++depth;
			if(stk.empty() || stk.top() < 0) stk.push(1);
			else stk.top()++;
		}else if(S[i] == '2') {
			++depth;
			if(stk.empty() || stk.top() > 0) stk.push(-1);
			else stk.top()--;
		}else if(S[i] == 'U') {
			--depth;
			assert(!stk.empty());
			int t = stk.top(); stk.pop();
			t = (t < 0) ? (t + 1) : (t - 1);
			if(t != 0) stk.push(t);
		}else if(S[i] == 'L') {
			// 1. 뒤에 있던 모든 1들을 지운다 (존재한다면)
			// 2. 지운 상태에서 가장 뒤에 있는 2 하나를 1로 바꾼다
			// 3. 지웠던 1들을 2로 치환해서 다시 넣는다

			assert(!stk.empty());
			int t = stk.top(); stk.pop();
			if(t > 0) { // stk.pop() 에 의해 1들을 다 지운 상태임
				if(!stk.empty()) { // 지운 상태에서 가장 뒤에 있는 2 하나를 1로 바꿈
					assert(stk.top() < 0);
					if(stk.top() == -1) {
						stk.pop();
						if(stk.empty()) stk.push(1);
						else stk.top()++;
					}else {
						stk.top()++;
						stk.push(1);
					}
				}
				// 지웠던 1들을 2로 치환함
				stk.push(-t);
			}else if(t < 0) { // 2번 과정
				stk.push(t);
				if(!stk.empty()) { // 지운 상태에서 가장 뒤에 있는 2 하나를 1로 바꿈
					assert(stk.top() < 0);
					if(stk.top() == -1) {
						stk.pop();
						if(stk.empty()) stk.push(1);
						else stk.top()++;
					}else {
						stk.top()++;
						stk.push(1);
					}
				}
			}else {
				assert(0);
			}
		}else if(S[i] == 'R') {
			// 1. 뒤에 있던 모든 2들을 지운다 (존재하면)
			// 2. 지운 상태에서 가장 뒤의 1을 2로 치환한다
			// 3. 지웠던 2들을 1로 치환해서 넣는다 (위랑 똑같이 하면 될듯?)

			assert(!stk.empty());
			int t = stk.top(); stk.pop();
			if(t < 0) { // stk.pop() 에 의해 2들을 다 지운 상태임
				if(!stk.empty()) { // 지운 상태에서 가장 뒤에 있는 1 하나를 2로 바꿈
					assert(stk.top() > 0);
					if(stk.top() == 1) {
						stk.pop(); 
						if(stk.empty()) stk.push(-1);
						else stk.top()--;
					}else {
						stk.top()--;
						stk.push(-1);
					}
				}
				// 지웠던 1들을 2로 치환함
				stk.push(-t);
			}else if(t > 0) { // 2번 과정
				stk.push(t);
				if(!stk.empty()) { // 지운 상태에서 가장 뒤에 있는 1 하나를 2로 바꿈
					assert(stk.top() > 0);
					if(stk.top() == 1) {
						stk.pop();
						if(stk.empty()) stk.push(-1);
						else stk.top()--;
					}else {
						stk.top()--;
						stk.push(-1);
					}
				}
			}else {
				assert(0);
			}
		}else {
			assert(0);
		}
	}

}

int main() {
	int i, j, k;

	scanf("%s%s", A+1, B+1);
	AN = strlen(A+1);
	BN = strlen(B+1);

	convert (A, AN, PS, PD);
	convert (B, BN, QS, QD);
	
	if(PD > QD) swap(PS, QS), swap(PD, QD);

	while(PD < QD) {
		++depth; --QD;
		int t = QS.top(); QS.pop();
		t = (t < 0) ? (t + 1) : (t - 1);
		if(t != 0) QS.push(t);
	}

	while(!PS.empty()) {
		int t = PS.top(); PS.pop();
		int s = (t > 0) ? 1 : 2;
		t = abs(t);
		while(t--) P[++PN] = s;
	}

	while(!QS.empty()) {
		int t = QS.top(); QS.pop();
		int s = (t > 0) ? 1 : 2;
		t = abs(t);
		while(t--) Q[++QN] = s;
	}

	reverse(P+1, P+PN+1);
	reverse(Q+1, Q+QN+1);

	res = PN+PN;

	ll val = 0;
	for(i = 1; i <= PN; i++) {
		val *= 2;
		val += P[i] - Q[i];
		if(val > (1ll<<30)) break;
		res = min(res, 2 * (PN-i) + abs(val));
	}

	res += depth;
	printf("%d\n", res);
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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