hpnq

Untitled

Oct 22nd, 2023
1,015
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. //speed coding
  3.  
  4. #define mp make_pair
  5. #define cve(tpy) for (auto i : tpy) {for(auto j : i){cout << j << " ";  }cout << "\n";} ;
  6. #define f first
  7. #define s second
  8. #define loop(i, x, n) for (int i = x; i < n; i++)
  9. #define joop(x, n) for (ll j = x; j < n; j++)
  10. #define lp(n) for (ll i = 0; i < n; i++)
  11. #define err cout << "ERROR" << endl;
  12. #define all(x) x.begin(), x.end()
  13. #define pb push_back
  14. #define sz(x) x.size()
  15. #define rndm rng()
  16.  
  17. // types
  18. #define pii pair<int, int>
  19. #define pll pair<ll, ll>
  20. #define vvi vector<vector<int>>
  21. #define vvll vector<vector<ll>>
  22. typedef long long ll;
  23. typedef long double ld;
  24.  
  25. // types of data
  26. #define inf 1000000000
  27. #define infll 1000000000000000000
  28. #define INF ll(1e18)
  29.  
  30. #define md 998244353
  31. #define mod 1000000009
  32. //#define K 239017
  33.  
  34. #define DEBUG 1
  35. using namespace std;
  36. mt19937_64 rng(113113);
  37. uniform_int_distribution<ll> drist;
  38.  
  39.  
  40. void solve() {
  41.     int a, b;
  42.     cin >> a >> b;
  43.     vector<pii > p(b + 1, mp(inf, -1));
  44.     if (a > b) {
  45.         cout << "-1\n";
  46.         return;
  47.     }
  48.     p[a] = mp(0, -1);
  49.     loop(i, a, b + 1) {
  50.         if (i * 2 <= b) {
  51.             int x = min(p[i].f + 1, p[2 * i].f);
  52.             if (x == p[i].f + 1) {
  53.                 p[2 * i] = mp(p[i].f + 1, 0);
  54.  
  55.             }
  56.         }
  57.         if (i * 10 + 1 <= b) {
  58.             int x = min(p[i].f + 1, p[i * 10 + 1].f);
  59.             if (x == p[i].f + 1) {
  60.                 p[i * 10 + 1] = mp(p[i].f + 1, 1);
  61.  
  62.             }
  63.         }
  64.     }
  65.     for (auto i: p) {
  66. //        cout << i << " ";
  67.     }
  68.     if(p[b].f != inf){
  69.         cout << p[b].f << "\n";
  70.         vector<int> ans;
  71.         while(b != a){
  72.             if(p[b].s == 0 ){
  73.                 ans.pb(0);
  74.                 b/=2;
  75.             }else if(p[b].s == 1 ){
  76.                 ans.pb(1);
  77.                 b= (b-1)/10;
  78.             }
  79.         }
  80.         reverse(all(ans));
  81.         for(auto i : ans){
  82.             cout << i << " ";
  83.         }
  84.  
  85.     }
  86. }
  87.  
  88.  
  89. int main() {
  90.     ios::sync_with_stdio(0);
  91.     cin.tie(0);
  92. #ifdef DEBUG
  93.     freopen("text.txt", "r", stdin);
  94. #endif
  95.     int t = 1;
  96. //    cin >> t;
  97.     loop(i, 0, t) {
  98.         solve();
  99.  
  100.     }
  101.  
  102.     return 0;
  103. }
  104.  
Advertisement
Add Comment
Please, Sign In to add comment