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;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
string parse(string S) {
vector<int> carry = { 0 };
vector<int> T = { 1 };
for (auto& c : S) {
switch (c) {
case '1':
T.push_back(0);
carry.push_back(0);
break;
case '2':
T.push_back(1);
carry.push_back(0);
break;
case 'L':
--carry.back();
break;
case 'R':
++carry.back();
break;
case 'U':
int spill = floor((carry.back() + T.back()) / 2.0);
T.pop_back();
carry.pop_back();
carry.back() += spill;
break;
}
}
//cout << "T: "; for (int x : T) { cout << x << " "; } cout << endl;
//cout << "C: "; for (int x : carry) { cout << x << " "; } cout << endl;
reverse(ALL(T));
reverse(ALL(carry));
FOR(i,0,SZ(T)-1) {
int cur = (T[i] + carry[i] + (1<<20)) % 2;
int spill = floor((T[i] + carry[i]) / 2.0);
T[i] = cur;
if (spill) { if (i == SZ(T)-1) T.push_back(0), carry.push_back(spill); else carry[i+1] += spill; }
}
//cout << "T: "; for (int x : T) { cout << x << " "; } cout << endl;
//cout << "C: "; for (int x : carry) { cout << x << " "; } cout << endl;
T.pop_back();
reverse(ALL(T));
string t = "";
for (auto& c : T) t += '0'+c;
return t;
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
string A, B; cin >> A >> B;
A = parse(A), B = parse(B);
int ans = 2e5+10;
if (A > B) swap(A,B);
//cout << A << " " << B << endl;
int diff = 0;
for (int l = 0; diff < ans && l < (int)min(A.length(),B.length()); ++l) {
diff *= 2;
diff += B[l]-A[l];
//cout << diff << " " << (int)A.length()-1-l << " " << (int)B.length()-1-l << endl;
ans = min(ans, diff + (int)A.length()-1-l + (int)B.length()-1-l);
}
cout << ans << endl;
}
# | 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... |