Cod sursa(job #1757857)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 15 septembrie 2016 23:19:47
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#define VAL 30005

using namespace std;

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

int N, i, p, x, be, a;
int aib[VAL], dif, K;

int zero(int x)
{
    return x&(-x);
}

void update(int i)
{
    while (i<=N)
    {
        aib[i]++;
        i+=zero(i);
    }
}

void scade(int i)
{
    while (i<=N)
    {
        aib[i]--;
        i+=zero(i);
    }
}

int verif(int a, int p)
{
    int x=0;
    int y=0;
    while (p!=0)
    {
        x+=aib[p];
        p-=zero(p);
    }
    while (a!=0)
    {
        y+=aib[a];
        a-=zero(a);
    }
    return y-x;
}

int cautbin(int be, int en, int dif)
{
    int mid, ans;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (verif(mid, K-1)>=dif)
        {
            if (verif(mid, K-1)==dif)
              ans=mid;
            en=mid-1;
        }
        else
          be=mid+1;
    }
    return ans;
}

int main()
{
    fin >> N;
    for (i=1; i<=N; i++)
      update(i);
    p=1;
    for (i=1; i<=N; i++)
    {
        p++;
        if (p>N)
          p=1;
        x=verif(N, p-1);
        if (x<i)
        {
            be=1;
            dif=i-x;
        }
        else
        {
            be=p;
            dif=i;
        }
        if (dif>N-i+1)
        {
            a=dif / (N-i+1);
            dif-=a*(N-i+1);
            if (dif==0)
              dif=N-i+1;
        }
        K=be;
        p=cautbin(be, N, dif);
        scade(p);
        fout << p << " ";
    }
    fin.close();
    fout.close();
    return 0;
}