Cod sursa(job #1438130)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 19 mai 2015 00:59:33
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int N,Partial[30005];
void Update(int initial,int value)
{
    int i=initial;
    while(i<=N)
    {
        Partial[i]+=value;
        i+=i&(-i);
    }
}
int Calculate_Sum_from_1(int a)
{
    int i=a,result=0;
    while(i>0)
    {
        result+=Partial[i];
        i-=i&(-i);
    }
    return result;
}
int Calculate_Sum(int a,int b)
{
    return Calculate_Sum_from_1(b)-Calculate_Sum_from_1(a-1);
}

void Solve()
{
    int last=2;
    for(int i=1;i<=N;i++)
    {
        int step=i;
        while(N-i+1<step)
            step-=N-i+1;
        int L,left=last,right=N,sol=0;
        int sum=Calculate_Sum(last,N);
        if(sum<step)
            left=1,right=last-1,step-=sum;
        L=left;
        while(L<=right)
        {
            int mid=(L+right)/2;
            if(Calculate_Sum(left,mid)>=step)
            {
                right=mid-1;
                sol=mid;
            }
            else
                L=mid+1;
        }
        g<<sol<<" ";
        last=sol;
        if(sol!=0)
        Update(sol,-1);
    }
}
int main()
{
    f>>N;
    for(int i=1;i<=N;i++)
        Update(i,1);
    Solve();
    return 0;
}