Cod sursa(job #2290215)

Utilizator Paul_BalanPavel Balan Paul_Balan Data 25 noiembrie 2018 23:36:16
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,t[30000];

void update(int idx){
    for(; idx<=n; idx+=(idx&-idx))
        t[idx]++;
}

int get(int idx){
    int res=0;
    for(;idx;idx-=(idx&-idx))
        res+=t[idx];
    return res;
}

int main()
{
    in >> n;
    int x = 2;
    for(int i=1, cn=n; i<=n; i++, cn--){
        x = (x-1+i)%cn;
        if(x==0) x = cn;
        int lo=1, hi=n;
        while(lo<hi){
            int mi=(lo+hi)/2;
            if(mi-get(mi)<x) lo = mi+1;
            else hi=mi;
        }
        update(lo);
        out << hi << "  ";
    }
}