Cod sursa(job #3248360)

Utilizator stefanvilcescuStefan Vilcescu stefanvilcescu Data 11 octombrie 2024 16:06:00
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <math.h>

const int MAXN=3e4;
const int MAXBIT=15;

struct BIT{
    int aib[MAXN+1], n, i;
    void init(int _n){
        this->n=_n;
        for(i=0; i<=n; i++)
            aib[i]=i&-i;
    }
    void update_pref_sum(int poz, int val){
        update(poz, val);
    }
    void update(int poz, int val){
        for(; poz<=n; poz+=poz&-poz)
            aib[poz]+=val;
    }
    int get_pref_sum(int poz){
        return query(poz);
    }
    int query(int poz){
        int ans=0;
        for(; poz>0; poz&=(poz-1))
            ans+=aib[poz];
        return ans;
    }
    int bin_search(int k){
        int ans=0;
        for(i=MAXBIT; i>=0; i--)
            if(ans+(1<<i)<=n && aib[ans+(1<<i)]<k)
                k-=aib[ans+=(1<<i)];
        return ans+1;
    }
};

BIT aib;

int main()
{
    std::ifstream cin("order.in");
    std::ofstream cout("order.out");
    int n, cate, poz, last, x, i;
    cin>>n;
    aib.init(n);
    cout<<"2 ";
    aib.update_pref_sum(2, -1);
    last=2;
    for(i=1; i<n; i++){
        cate=(n-i);
        poz=i%(n-i)+1;
        x=aib.get_pref_sum(last);
        if(cate-x>=poz)
            last=aib.bin_search(x+poz);
        else
            last=aib.bin_search(poz-(cate-x));
        cout<<last<<" ";
        aib.update_pref_sum(last, -1);
    }
    return 0;
}