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<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl
typedef long long ll;
typedef pair<int, int> point;
vector <int> a, b;
string sa, sb;
const int off = 1 << 17;
void update(string &s, vector <int> &v){
for(auto it : s){
if(it == '1')
v.pb(0);
else if(it == '2')
v.pb(1);
else if(it == 'L')
v.back() --;
else if(it == 'R')
v.back() ++;
else{
int x = v.back();
v.pop_back();
if(x >= 0){
v.back() += x / 2;
}
else{
v.back() += x / 2;
x -= x / 2 * 2;
if(x < 0){
v.back() --;
}
}
}
}
}
void prop(vector <int> &v){
for(int i = sz(v) - 1; i > 0; --i){
int x = v[i];
if(x >= 0){
v[i - 1] += v[i] / 2;
v[i] %= 2;
}
else{
v[i - 1] += v[i] / 2;
v[i] -= v[i] / 2 * 2;
if(v[i] < 0){
v[i - 1] --;
v[i] += 2;
}
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> sa >> sb;
update(sa, a);
update(sb, b);
prop(a); prop(b);
ll tmp = sz(a) + sz(b), dist = 0;
ll sol = tmp;
REP(i, min(sz(a), sz(b))){
dist <<= 1;
dist += b[i] - a[i];
tmp -= 2;
sol = min(sol, tmp + abs(dist));
if(dist > 1e13)
break;
}
cout << sol;
}
# | 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... |