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, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
using ll=long long;
using ld=long double;
template <typename T> inline void read(T &x){
char c;
bool nega=0;
while((!isdigit(c=getchar()))&&(c!='-'));
if(c=='-'){
nega=1;
c=getchar();
}
x=c-48;
while(isdigit(c=getchar())) x=x*10+c-48;
if(nega) x=-x;
}
template <typename T> inline void writep(T x){
if(x>9) writep(x/10);
putchar(x%10+48);
}
template <typename T> inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
writep(x);
}
template <typename T> inline void writeln(T x){
write(x);
putchar('\n');
}
#define taskname "Board"
class number{
protected:
vector <pair <int, int>> v;
void append_zero(int sz=1){
if(sz==0) return;
if(v.back().first==0) v.back().second++;
else v.pb(mp(0, sz));
}
void append_one(int sz=1){
if(sz==0) return;
if(v.back().first==1) v.back().second++;
else v.pb(mp(1, sz));
}
void truncate(){
v.back().second--;
if(v.back().second==0) v.pop_back();
}
void take_one(){
int added_one=0;
if(v.back().first==0){
added_one+=v.back().second;
v.pop_back();
}
v.back().second--;
if(v.back().second==0) v.pop_back();
append_zero();
append_one(added_one);
}
void add_one(){
int added_zero=0;
if(v.back().first==1){
added_zero+=v.back().second;
v.pop_back();
}
v.back().second--;
if(v.back().second==0) v.pop_back();
append_one();
append_zero(added_zero);
}
public:
number(){
v.clear();
v.pb(mp(0, 1));
}
void left_child(){
append_zero();
}
void right_child(){
append_one();
}
void parent(){
truncate();
}
void left_cousin(){
take_one();
}
void right_cousin(){
add_one();
}
void process_token(char c){
if(c=='1') left_child();
else if(c=='2') right_child();
else if(c=='U') parent();
else if(c=='L') left_cousin();
else right_cousin();
}
void input(){
string s;
cin>>s;
for(auto c: s) process_token(c);
}
deque <int> get_uncompresed_form(){
deque <int> res;
for(auto x: v) FFOR(j, 0, x.second) res.pb(x.first);
return res;
}
} A, B;
deque <int> x, y;
int main(){
#ifdef Uiharu
if(fopen(taskname".in", "r"))
freopen(taskname".in", "r", stdin);
#endif // Uiharu
A.input();
B.input();
x=A.get_uncompresed_form();
y=B.get_uncompresed_form();
while((!x.empty())&&(!y.empty())&&(x.front()==y.front())){
x.pop_front();
y.pop_front();
}
int ans=x.size()+y.size();
int px=0, py=0;
FFOR(i, 0, min(x.size(), y.size())){
px=px*2+x[i];
py=py*2+y[i];
if(abs(px-py)>=ans) break;
ans=min(ans, (int)(abs(px-py)+x.size()-i-1+y.size()-i-1));
}
writeln(ans);
}
Compilation message (stderr)
board.cpp: In function 'int main()':
board.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
^
board.cpp:136:5: note: in expansion of macro 'FFOR'
FFOR(i, 0, min(x.size(), y.size())){
^~~~
# | 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... |