Cod sursa(job #2265670)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 21 octombrie 2018 15:38:33
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>
/// TONI BO$$ was here
/// #MLC
using namespace std;
int aib[30001],n;

int zeros(int x)
{
    return (x^(x-1))&x;
}

void update(int i,int x)
{
    for(int ct=i; ct<=n; ct+=zeros(ct))
        aib[ct]+=x;
}

int query(int i)
{
    int rez=0;
    for(int ct=i; ct>0; ct-=zeros(ct))
        rez+=aib[ct];
    return rez;
}

int main()
{
    int i,k,ct,z,pas,j;
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        update(i,1);
    k=1;
    for(i=1,ct=n; i<=n; i++,ct--)
    {
        z=(i-1)%ct+1;
        if(query(n)-query(k)<z)
        {
            z-=(query(n)-query(k));
            pas=1<<14;
            j=0;
            while(pas)
            {
                if(j+pas<=k && query(j+pas)<z)
                    j+=pas;
                pas/=2;
            }
            printf("%d ",j+1);
            update(j+1,-1);
            k=j+1;
            continue ;
        }
        j=k;
        pas=1<<14;
        while(pas)
        {
            if(j+pas<=n && query(j+pas)-query(k)<z)
                j+=pas;
            pas/=2;
        }
        printf("%d ",j+1);
        k=j+1;
        update(j+1,-1);
    }

    return 0;
}