Cod sursa(job #1457475)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 3 iulie 2015 14:05:23
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int sol,st,dr,n,mij,sum,i,last,l,step,AI[30009];
int zeros(int x)
{
    return (x^(x-1))&x;
}
void update(int poz,int val)
{
    while(poz<=n)
    {
        AI[poz]+=val;
        poz+=zeros(poz);
    }
}
int suma(int poz)
{
    int s=0;
    while(poz)
    {
        s+=AI[poz];
        poz-=zeros(poz);
    }
    return s;
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i) update(i,1);
    last=2;
    for(i=1;i<=n;++i)
    {
        step=i; sol=0;
        while(n-i+1<step) step-=n-i+1;
        sum=suma(n)-suma(last-1);
        st=last; dr=n;
        if(sum<step) {st=1; dr=last-1; step-=sum;}
        l=st;
        while(l<=dr)
        {
            mij=(l+dr)/2;
            if(suma(mij)-suma(st-1)>=step)
            {
                dr=mij-1;
                sol=mij;
            }
            else l=mij+1;
        }
        g<<sol<<" ";
        last=sol;
        update(sol,-1);
    }
    g.close();
    return 0;
}