Cod sursa(job #2046489)

Utilizator alexandruilieAlex Ilie alexandruilie Data 23 octombrie 2017 20:40:41
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int n,nrcopii,poz=2,x,sol[30001],aib[30001];
void adun(int x,int val)
{
    int i;
    for(i=x;i<=n;i+=i&(-i))
        aib[i]+=val;
}
int sum(int x)
{
    int s=0,i;
    for(i=x;i>=1;i-=i&(-i))
        s+=aib[i];
    return s;
}
int cautbinar(int poz)
{
    int st=1,suma,dr=n,mid,minim=n+1;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        suma=sum(mid);
        if(suma==poz&&mid<minim) minim=mid;
        else if(suma>=poz) dr=mid-1;
        else st=mid+1;
    }
    return minim;
}
int main()
{
    int i;
    f>>n;
    for(i=1;i<=n;i++) adun(i,1);
    nrcopii=n;
    for(i=1;i<=n;i++)
    {
        nrcopii--;
        x=cautbinar(poz);
        adun(x,-1);
        sol[i]=x;
        poz+=i;
        if(nrcopii)
            if(poz%nrcopii) poz=poz%nrcopii;
        else poz=nrcopii;
    }
    for(i=1;i<=n;i++) g<<sol[i]<<' ';
    return 0;
}