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;
/// 11:09
const int Nmax = 1e5 + 5;
int n, m;
int ans = 0;
char A[Nmax], B[Nmax], aux[Nmax];
int d[Nmax];
void trans(char A[], int &n)
{
int i, j, s = 0;
for(i=1; i<=n; ++i)
if(A[i] == 'L' || A[i] == 'R')
{
int nr = 0;
while(i<=n && (A[i] == 'L' || A[i] == 'R'))
{
if(A[i] == 'L') ++nr;
else --nr;
++i;
}
--i;
for(j=1; j<=nr; ++j) aux[++s] = 'L';
for(j=1; j<=-nr; ++j) aux[++s] = 'R';
}
else aux[++s] = A[i];
n = s;
for(i=1; i<=n; ++i) A[i] = aux[i];
s = 0;
int last = 0;
d[0] = -1;
for(i=1; i<=n; ++i)
if(A[i] == 'U')
{
if(d[s] == s-1) last ^= 1;
--s;
}
else if(A[i] == '1')
{
++s;
if(last == 0) d[s] = d[s-1];
else d[s] = s-1;
last = 0;
}
else if(A[i] == '2')
{
++s;
if(last == 1) d[s] = d[s-1];
else d[s] = s-1;
last = 1;
}
else if(A[i] == 'L')
{
if(last == 1)
{
last = 0;
if(d[s] == s-1) d[s] = d[s-1];
else d[s] = s-1;
}
else
{
last = 1;
int node = d[s];
if(d[node] == node-1) d[node] = d[node-1];
else d[node] = node - 1;
}
}
else if(A[i] == 'R')
{
if(last == 0)
{
last = 1;
if(d[s] == s-1) d[s] = d[s-1];
else d[s] = s-1;
}
else
{
last = 0;
int node = d[s];
if(d[node] == node-1) d[node] = d[node-1];
else d[node] = node - 1;
}
}
n = s;
for(i=1; i<=n; ++i)
{
if(d[i] == -1) A[i] = 0;
else A[i] = A[d[i]] ^ 1;
}
}
void read()
{
cin >> (A+1) >> (B+1);
n = strlen(A+1);
m = strlen(B+1);
trans(A, n);
trans(B, m);
if(n > m) ans += n - m, n = m;
else ans += m - n, m = n;
int i, p = 0;
while(A[p+1] == B[p+1] && p < n) ++p;
for(i=1; i<=n-p; ++i)
A[i] = A[i+p], B[i] = B[i+p];
n -= p;
}
int solve()
{
if(n == 0) return 0;
int i;
if(A[1] > B[1])
for(i=1; i<=n; ++i) swap(A[i], B[i]);
for(i=2; i<=n; ++i) A[i] ^= 1;
B[1] = 0;
int x = 0, y = 0;
int ans = 2 * n;
for(i=0; i<=n; ++i)
{
ans = min(ans, x + y + 2 * (n-i) + 1);
x = 2 * x + A[i+1];
y = 2 * y + B[i+1];
if(x + y > ans) break;
}
return ans;
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false); cin.tie(0);
read();
ans += solve();
cout << ans << '\n';
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... |