| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 320649 |
2020-11-09T11:53:52 Z |
monus1042 |
Board (CEOI13_board) |
C++17 |
|
2 ms |
748 KB |
// NK
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef pair<int,int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define psf push_front
#define pof pop_front
#define mkp make_pair
#define mkt make_tuple
#define all(x) x.begin(), x.end()
#define Bolivia_is_nice ios::sync_with_stdio(false), cin.tie(nullptr)
//typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ord_set;
ll locationof(string s, ll nod, ll & lev){
for (int i=0; i<s.size(); i++){
if (s[i] == '1'){
nod = nod*2;
lev++;
}else if (s[i] == '2'){
nod = nod*2 + 1;
lev++;
}else if (s[i] == 'U'){
nod = nod / 2;
--lev;
}else if (s[i] == 'L'){
nod = nod - 1;
}else{ // R
nod = nod + 1;
}
}
return nod;
}
vll f(ll nod){
vll v;
while(1){
v.pb(nod);
if (nod / 2 > 0){
nod /= 2LL;
}else break;
}
return v;
}
void solve(){
string a,b; cin>>a>>b;
ll AL = 0, BL = 0;
ll A = locationof(a, 1ll, AL), B = locationof(b, 1ll, BL);
//int MAXsteps = 50 * 2 + 2;
ll Log = 52;
if (AL < BL) swap(A, B), swap(AL, BL);
ll ans = AL - BL;
for (ll i = 0; i<ans; i++){
AL--;
A/=2LL;
}
//cout<<ans<<endl;
//cout<<AL<<endl<<BL<<endl;
if (A > B) swap(A, B);
vll lca = f(B);
int it = 0;
ll curr = 0;
ll Answer = 8e18;
while(1){
// first do try with current height
if ((ll)it == (ll)lca.size()) break;
ll HOR = lca[it] - A;
if (HOR >= 0){
ll temp = curr + HOR + (ll)it + ans;
Answer = min(Answer, temp);
}else break;
// then climb:
ll par = A/2;
if (par * 2 == A && par > 0){ // A is left child
curr++;
A = par;
}else if (par * 2 + 1 == A && par > 0){ // A is right child
//move R
bool ok = 0;
for (ll bit = 0; bit < Log; ++bit){
if ( (ll)((1LL << bit)-1LL) == A) ok = 1;
}
if (!ok){
++curr;
A++;
par = A / 2;
if (par > 0){
++curr;
A = par;
}
}else{
break;
}
}else break;
++it;
}
cout<<Answer<<'\n';
}
int main(){
Bolivia_is_nice;
int t = 1; //cin>>t;
while(t--)
solve();
return 0;
}
/*
~/.emacs
*/
Compilation message
board.cpp: In function 'll locationof(std::string, ll, ll&)':
board.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int i=0; i<s.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
