Labyrintti

#include <iostream>
using namespace std;
long long x1, y1, x2, y2;
 
 
long long Abs(long long a){ return a>0?a:-a;}
 
 
 
 
pair<long long, long long> dp(int s){
  long long x=-1; long long y=1;
  for (int i=4; i<s; ++i){
    if (i==4) y-=2;
    else if (i==5) x+=4;
    else{
    if (i%4==0) y-=(1LL<<(i-4))+2;
    if (i%4==1) x+=(1LL<<(i-4))+2;
    if (i%4==2) y+=(1LL<<(i-4))+2;
    if (i%4==3) x-=(1LL<<(i-4))+2;
    }
  }
  return make_pair(x, y);
}
 
int ft(long long x, long long y){
  int s=4;
  long long d=0; 
  long long r=2; 
  long long u=4; 
  long long l=-6;
  
  long long x1=l;
  long long x2=r;
  long long y1=d+1;
  long long y2=u;
  while (!(x1<=x && x<=x2 && y1<=y && y<=y2)){
   // cout << s << ": " << x1 << " " << x2 << " " << y1 << " " << y2 << endl;
    if (s%4==0){ //alas
      d=u-(1LL<<s);
      y1=d;
      x2=r-(1LL<<(s-3))-1;
    }
    if (s%4==1){ // oik
      r=l+(1LL<<s);
      x2=r;
      y2=u-(1LL<<(s-3))-1;
    }
    if (s%4==2){ // yl
      u=d+(1LL<<s);
      y2=u;
      x1=l+(1LL<<(s-3))+1;
    }
    if (s%4==3){ // v
      l=r-(1LL<<s);
      x1=l;
      y1=d+(1LL<<(s-3))+1;
    }
    ++s;
  }
  return s;
}
 
int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  /*
  for (int y=6; y>=-16; --y){
    for (int x=-9; x<=6; ++x){
      if (dp(ft(x, y)).first==x && dp(ft(x, y)).second==y) cout << "X" << " ";
      else cout << ft((long long)x, (long long)y) << " ";
    }cout << endl;      
  }
  //*/
  
  
  cin >> y1 >> x1 >> y2 >> x2; y1=-y1; y2=-y2;
  
  int s1=ft(x1, y1);
  int s2=ft(x2, y2);
  
  long long ans=0;
  if (s1==s2 || Abs(s2-s1)==1){
    ans=Abs(x2-x1)+Abs(y1-y2);
  }else if (s1>s2){--s1;
    long long x=dp(s2).first;
    long long y=dp(s2).second;
    ans+=Abs(x2-x)+Abs(y2-y);
    x=dp(s1).first;
    y=dp(s1).second;
    ans+=Abs(x1-x)+Abs(y1-y);
    for (int i=s2; i<s1; ++i) ans+=(1LL<<(i-4))+2;
  if (s2==4)  --ans;
  }else{--s2;
    long long x=dp(s1).first;
    long long y=dp(s1).second;
    ans+=Abs(x1-x)+Abs(y1-y);
    x=dp(s2).first;
    y=dp(s2).second;
    ans+=Abs(x2-x)+Abs(y2-y);
    for (int i=s1; i<s2; ++i) ans+=(1LL<<(i-4))+2;
   if (s1==4) --ans;
  }
  cout << ans << endl;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED