#include<bits/stdc++.h>
using namespace std;
struct num{
deque<int> a;
int dep;
num(){
a = {0};
dep = 0;
}
void mult2(){
a.push_back(0);
}
void div2(){
assert(a.size() > 0);
a.pop_back();
}
void inc(){
if(a.size() == 0){
a.push_back(1); return;
}
a.back() += 1;
int pntr = a.size()-1;
while(pntr > 0 && a[pntr] > 1){
a[pntr] = 0;
a[pntr-1] += 1;
pntr--;
}
if(a[0] > 1){
a.push_front(1);
a[1] = 0;
}
}
void dec(){
int pntr = a.size()-1;
for(; pntr >= 0 && a[pntr] == 0; pntr--);
assert(a[pntr] == 1);
a[pntr] = 0;
for(pntr++; pntr < a.size(); pntr++){
a[pntr] = 1;
}
}
void clearLeadingZero(){
while(a.size() && a[0] == 0){
a.pop_front();
}
}
void print(){
for(int i = 0; i < a.size(); i++){
cout<<a[i];
}
cout<<endl;
}
};
void SWAP(num& a, num& b){
swap(a.a, b.a);
swap(a.dep, b.dep);
}
void move(num& a, char t){
if(t == '1'){
a.mult2();
a.dep++;
}else if(t == '2'){
a.mult2();
a.inc();
a.dep++;
}else if(t == 'U'){
a.div2();
a.dep--;
}else if(t == 'L'){
a.dec();
}else if(t == 'R'){
a.inc();
}else{
assert(false);
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
num a, b;
string ainp, binp;
cin>>ainp>>binp;
for(int i = 0; i < ainp.length(); i++){
move(a, ainp[i]);
}
for(int i = 0; i < binp.length(); i++){
move(b, binp[i]);
}
a.clearLeadingZero();
b.clearLeadingZero();
if(a.dep > b.dep){ //A is closer to the root
SWAP(a, b);
}
int ans = 0;
while(b.dep > a.dep){
move(b, 'U');
ans++;
}
//now they are at the same level
assert(a.dep == b.dep);
if(a.a.size() > b.a.size()){ // a has lesser size
SWAP(a, b);
}
while(a.a.size() < b.a.size()){
a.a.push_front(0);
}
a.a.push_front(0);
b.a.push_front(0);
assert(a.a.size() == b.a.size());
int lca = 0;
for(int i = 0; i < a.a.size(); i++){
if(a.a[i] != b.a[i]){
lca = i-1;
break;
}
}
if(a.a == b.a){
cout<<ans<<endl;
return 0;
}
if(a.a[lca+1] > b.a[lca+1]){ //a is smaller
SWAP(a, b);
}
assert(false);
int dist = 0;
int bestAns = (a.a.size() - lca + 10)*2;
for(int i = lca; i < a.a.size(); i++){
dist = dist*2 + (b.a[i] - a.a[i]);
int curAns = dist + (a.a.size()-i-1)*2;
if(curAns > 3e5) break;
bestAns = min(bestAns, curAns);
}
cout<<bestAns + ans<<endl;
}
Compilation message
board.cpp: In member function 'void num::dec()':
board.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(pntr++; pntr < a.size(); pntr++){
~~~~~^~~~~~~~~~
board.cpp: In member function 'void num::print()':
board.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a.size(); i++){
~~^~~~~~~~~~
board.cpp: In function 'int main()':
board.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ainp.length(); i++){
~~^~~~~~~~~~~~~~~
board.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < binp.length(); i++){
~~^~~~~~~~~~~~~~~
board.cpp:126:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a.a.size(); i++){
~~^~~~~~~~~~~~
board.cpp:142:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = lca; i < a.a.size(); i++){
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
788 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1069 ms |
768 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
768 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1062 ms |
640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
