Cod sursa(job #2673956)

Utilizator tomaionutIDorando tomaionut Data 18 noiembrie 2020 11:57:17
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int aib[30005],n;
void Update(int p, int x)
{
    while (p<=n)
    {
        aib[p]+=x;
        p+=(p&(-p));
    }
}
int Suma(int p)
{
    int s=0;
    while (p>0)
    {
        s+=aib[p];
        p-=(p&(-p));
    }
    return s;
}
int CautBin(int val, int x)
{
    int st=x,dr=n,sol,mij,y;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        y=Suma(mij)-Suma(x-1);
        if (y==val)
        {
            sol=mij;
            dr=mij-1;
        }
        else if (y>val) dr=mij-1;
        else st=mij+1;
    }
    return sol;
}
int main()
{
    int i,j,x,poz=1,y;
    fin >> n;
    for (i=1; i<=n; i++)
        Update(i,1);
    for (i=1; i<=n; i++)
    {
        x=Suma(n)-Suma(poz);
        if (x>=i)
        {
            poz=CautBin(i,poz+1);
            Update(poz,-1);
            fout << poz << " ";
        }
        else
        {
            x=i-x;
            y=x%(n-i+1);
            if (y==0) y=n-i+1;
            poz=CautBin(y,1);
            fout << poz << " ";
            Update(poz,-1);
        }
    }



    return 0;
}