NKGIFTS - VOI08 Quà tết

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>

#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
#define ll long long
#define P pair<ll,ll>
#define F first
#define S second
#define BASE 1000000000000000LL
#define LBASE 15
using namespace std;

int debug=0;
int k;
P lt2[80],i,j,one;

P operator + (P a,P b) {
    P c;
    c.S = a.S + b.S;
    int nho;
    if (c.S>=BASE) {
        nho=1;
        c.S-=BASE;
    }
    else nho=0;
    c.F = a.F + b.F + nho;
    return c;
}

P operator - (P a,P b) {
    P c;
    c.S = a.S - b.S;
    int nho;
    if (c.S>=0) nho=0;
    else {
        nho=1;
        c.S += BASE;
    }
    c.F = a.F - b.F - nho;
    return c;
}

P operator * (P a,ll k) {
    P c;
    c.S = a.S * k;
    int nho=c.S/BASE;
    c.S%=BASE;
    c.F = a.F * k + nho;
    return c;
}

void print(P a) {
    if (a.F) {
        cout<<a.F;
        char s[20];
        sprintf(s,"%lld",a.S);
        FOR(i,1,LBASE-strlen(s)) cout<<"0";
    }
    cout<<a.S;
}

void init() {
    lt2[0].S = 1;
    FOR(i,1,80)
        lt2[i]=lt2[i-1]*2;
        
    if (debug) FOR(i,0,80) print(lt2[i]);
}

void get(int u,P i,P j,P pos) {
    P res;
    if (u==0) {
        print(pos);
        return ;
    }
    if (i<lt2[u-1]) pos = pos+lt2[2*k-2*u];
    else {
        i = lt2[u]-i-one;
        pos = lt2[2*k - 2*u] + one - pos;
    }
    
    if (j<lt2[u-1]) {
        j = lt2[u-1]-j-one;
        pos = lt2[2*k - 2*u +1]+one-pos;
    }
    else {
        pos = pos+lt2[2*k-2*u+1];
        j = j - lt2[u-1];
    }
    
    get(u-1,i,j,pos);
}

void solve() {
    P pos;
    pos.F = 0; pos.S = 1;
    get(k,i,j,pos);
}

int main() {
    init();
    cin >>k;
    i.F = j.F = 0;
    one.F = 0; one.S = 1;
    cin >>i.S >>j.S;
    solve(); cout<<" ";
    cin >>i.S >>j.S;
    solve();
    return 0;
}

Download