As932

descompunere

Jan 15th, 2021
756
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2.  
  3. using namespace std;
  4.  
  5. ifstream cin("descompunere.in");
  6. ofstream cout("descompunere.out");
  7.  
  8. typedef long long ll;
  9.  
  10. ll ln, cl, ans;
  11.  
  12. void solve(ll l1, ll c1, ll l2, ll c2, ll l3, ll c3, int in){
  13.     int mdL;
  14.  
  15.     if(in == 1)
  16.         mdL = (l1 + l2) / 2;
  17.     else
  18.         mdL = (l1 + l3) / 2;
  19.  
  20.     if(mdL == l1){
  21.         if(in == 1){
  22.             if(ln == l1 && cl == c1)
  23.                 ans += 0;
  24.             else if(ln == l2 && cl == c2)
  25.                 ans += 1;
  26.             else if(ln == l3 && cl == c3)
  27.                 ans += 3;
  28.             else
  29.                 ans += 2;
  30.         } else {
  31.             if(ln == l1 && cl == c1)
  32.                 ans += 1;
  33.             else if(ln == l2 && cl == c2)
  34.                 ans += 3;
  35.             else if(ln == l3 && cl == c3)
  36.                 ans += 0;
  37.             else
  38.                 ans += 2;
  39.         }
  40.     } else {
  41.         if(in == 1){
  42.             if(l1 <= ln && ln <= mdL){
  43.                 ans += 0;
  44.                 solve(l1, c1, mdL, c1, mdL, mdL * 2 - 1, 1);
  45.             } else if(ln >= mdL + 1){
  46.                 ll lvl = (ln - mdL);
  47.                 ll cL = c2 + (lvl * 2 - 1) - 1;
  48.                 ll cR = c3 - (lvl * 2 - 1) + 1;
  49.  
  50.                 if(cl <= cL){
  51.                     ans += 1;
  52.                     solve(mdL + 1, c1, l2, c2, l2, cL, 1);
  53.                 } else if(cl >= cR){
  54.                     ans += 3;
  55.                     solve(mdL + 1, cR, l2, cR, l2, c3, 1);
  56.                 } else {
  57.                     ans += 2;
  58.                     solve(mdL + 1, c1 + 1, mdL + 1, cR - 1, l2, cL + 1, -1);
  59.                 }
  60.             }
  61.         } else {
  62.             if(mdL + 1 <= ln && ln <= l3){
  63.                 ans += 0;
  64.                 ll lvl = (l3 - l1 + 1) / 2;
  65.                 solve(mdL + 1, c3 - (lvl * 2 - 1) + 1, mdL + 1, c3, l3, c3, -1);
  66.             } else {
  67.                 ll cL = c2 / 2;
  68.  
  69.                 if(cl <= cL){
  70.                     ans += 1;
  71.                     solve(l1, c1, l2, cL, mdL, cL, -1);
  72.                 } else {
  73.                     ll lvl = ln - l1 + 1;
  74.                     int cR = cL + 1 + (lvl * 2 - 1) - 1;
  75.  
  76.                     if(cl <= cR){
  77.                         ans += 2;
  78.                         solve(l1, cL + 1, mdL, cL + 1, mdL, c2 - 1, 1);
  79.                     } else {
  80.                         ans += 3;
  81.                         solve(l1, cL + 2, l1, c2, mdL, c2, -1);
  82.                     }
  83.                 }
  84.             }
  85.         }
  86.     }
  87. }
  88.  
  89. int main()
  90. {
  91.     int n, m;
  92.  
  93.     cin >> n >> m;
  94.  
  95.     while(m--){
  96.         ans = 0;
  97.         cin >> ln >> cl;
  98.  
  99.         solve(1, 1, (1LL << n), 1, (1LL << n), (1LL << (n + 1)) - 1, 1);
  100.  
  101.         cout << ans << "\n";
  102.     }
  103.  
  104.     return 0;
  105. }
  106.  
RAW Paste Data