Cod sursa(job #3304168)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 21 iulie 2025 14:00:21
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>

using namespace std;

ifstream in("order.in");
ofstream out("order.out");

const int nmax = 30000;
int n, nrq, type, a, b;
int value;

inline int f(int x){ return (x & (-x)); }
struct fenwicktree{
    int tree[nmax + 2], intotal;
    void add(int pos, int val){
        for(int i = pos; i <= n; i += f(i))
            tree[i] += val;
        intotal += val;
    }

    int sum(int pos){
        int s = 0;
        for(int i = pos; i >= 1; i -= f(i))
            s += tree[i];
        return s;
    }

    int getkth(int k){
        int pos = 0;
        for(int b = 14; b >= 0; b--){
            if((pos | (1 << b)) <= n && tree[pos | (1 << b)] < k)
                pos |= (1 << b), k -= tree[pos];
        }
        return pos + 1;
    }
} aib;

int main(){

    in>>n; aib.intotal = n;
    for(int i = 1; i <= n; i++){
        aib.tree[i] += 1;
        if(i + f(i) <= n)
            aib.tree[i + f(i)] += aib.tree[i];
    }

    for(int i = 1, child = 1; i <= n; i++){
        int k = i + aib.sum(child);

        k %= aib.intotal;
        if(!k) k = aib.intotal;

        k = aib.getkth(k);
        aib.add(k, -1);

        out<<k<<" ";
        child = k;
    }

    return 0;
}