This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |