Cod sursa(job #2869721)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 11 martie 2022 19:43:40
Problema Fractal Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define fi first
#define se second
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(a) ((int)(a).size())
#define all(a) begin(a),end(a)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) std::cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) std::cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)std::cerr<<x[_]<<' ';std::cerr<<'\n',aaa
#define dbgs(x) std::cerr<<(#x)<<"[stl]: ";for(auto _:x)std::cerr<<_<<' ';std::cerr<<'\n',aaa
#define dbgp(x) std::cerr<<(#x)<<": "<<x.fi<<' '<<x.se<<'\n',aaa
#define dbgsp(x) std::cerr<<(#x)<<"[stl pair]:\n";for(auto _:x)std::cerr<<_.fi<<' '<<_.se<<'\n';aaa

using namespace std;

ifstream fin("fractal.in");
ofstream fout("fractal.out");

int sq(int x) {
  return x*x;
}

/**
fractal H[n] format din 4xH[n-1].
daca h[n] este parcurs asa: 0 3 (0 1 2 3)
                            1 2
atunci cei 4 fii se parcurg asa: (fiu I) 0 1 (0 3 2 1)
                                         3 2
(fii II si III) la fel ca tatal
(fiul IV) 2 3 (2 1 0 3)
          1 0
**/

int distTo(int n, int xl, int yl, int xh, int yh, int x, int y, int distYet, int *ord) {
  if (n == 0) return distYet;

  int xm = (xl + xh) / 2, ym = (yl + yh) / 2;

  if (x <= xm && y <= ym) { ///stanga sus
    ///cadranul stanga sus este vizitat al ord[0]-lea.
    distYet += ord[0] * sq(1<<(n-1));
    swap(ord[1], ord[3]);
    return distTo(n-1, xl, yl, xm, ym, x, y, distYet, ord);
  }

  if (x <= xm && y > ym) { ///stanga jos
    ///cadranul stanga jos este vizitat al ord[1]-lea.
    distYet += ord[1] * sq(1<<(n-1));
    return distTo(n-1, xl, ym+1, xm, yh, x, y, distYet, ord);
  }

  if (x > xm && y > ym) { ///dreapta jos
    ///cadranul dreapta jos este vizitat al ord[2]-lea.
    distYet += ord[2] * sq(1<<(n-1));
    return distTo(n-1, xm+1, ym+1, xh, yh, x, y, distYet, ord);
  }

  ///dreapta sus
  ///cadranul dreapta sus este vizitat al ord[3]-lea.
  distYet += ord[3] * sq(1<<(n-1));
  swap(ord[0], ord[2]);
  return distTo(n-1, xm+1, yl, xh, ym, x, y, distYet, ord);
}

int main() {
  int n, x, y; fin >> n >> x >> y; ///x pt coloana, y pt linie.
  int ord[4] = {0, 1, 2, 3};

  fout << distTo(n, 1, 1, (1<<n), (1<<n), x, y, 0, ord);

  fin.close();
  fout.close();

  return 0;
}