Cod sursa(job #3341453)

Utilizator Denis2Baran Denis-Constantin Denis2 Data 19 februarie 2026 17:03:00
Problema Fractal Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>
using namespace std;

long long hilbert(int k, long long x, long long y, int orient) {
    if (k == 0) return 0;

    long long half = 1LL << (k - 1);
    long long block = 1LL << (2 * (k - 1)); // numărul de puncte dintr-un cadran

    // determinăm cadranul
    int quad = 0;
    if (x <= half && y <= half) quad = 0;          // stânga-jos
    else if (x <= half && y > half) quad = 1;      // stânga-sus
    else if (x > half && y > half) quad = 2;       // dreapta-sus
    else quad = 3;                                 // dreapta-jos

    // transformăm cadranul în funcție de orientare
    static int trans[4][4] = {
        {0,1,2,3},
        {1,0,3,2},
        {2,3,0,1},
        {3,2,1,0}
    };

    int new_quad = trans[orient][quad];

    // orientările pentru fiecare cadran
    static int next_orient[4][4] = {
        {1,0,0,3},
        {0,1,1,2},
        {3,2,2,1},
        {2,3,3,0}
    };

    int new_orient = next_orient[orient][quad];

    // transformăm coordonatele în cadranul local
    long long nx = x, ny = y;

    if (quad == 0) {
        swap(nx, ny);
    } else if (quad == 1) {
        ny -= half;
    } else if (quad == 2) {
        nx -= half;
        ny -= half;
    } else {
        long long tx = nx - half;
        long long ty = ny;
        nx = half - ty + 1;
        ny = tx;
    }

    return new_quad * block + hilbert(k - 1, nx, ny, new_orient);
}

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

    int K;
    long long x, y;
    fin >> K >> x >> y;

    fout << hilbert(K, x, y, 0);

    return 0;
}