Cod sursa(job #2824260)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 31 decembrie 2021 19:37:45
Problema Fractal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

const int rotateDelta[4] = {3, 0, 0, 1};

long long gilbertOrder(int x, int y, int pow, int rotate) {
    if(pow == 0) 
        return 0;

    int hpow = 1 << (pow - 1);
    int seg = (x < hpow)? ((y < hpow)? 0 : 3) : ((y < hpow)? 1 : 2);

    seg = (seg + rotate) & 3;

    int nx = x & (x ^ hpow), ny = y & (y ^ hpow), nrot = (rotate + rotateDelta[seg]) & 3;

    long long subSquareSize = 1LL << (2 * pow - 2);
    long long ans = seg * subSquareSize;
    long long add = gilbertOrder(nx, ny, pow - 1, nrot);

    ans += (seg == 1 || seg == 2)? add : (subSquareSize - add - 1);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Open("fractal");

    int k, x, y; cin >> k >> x >> y;
    cout << gilbertOrder(y - 1, x - 1, k, 0);

    return 0;
}