Cod sursa(job #2777577)

Utilizator Alex_DiaconuDiaconu Alexandru Alex_Diaconu Data 23 septembrie 2021 18:36:38
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

ifstream ci ("order.in");
ofstream co ("order.out");

int n, v[30005];

void update(int p,int x)
{
    while(p<=n)
    {
        v[p]+=x;
        p+=(p&(-p));
    }
}

int suma(int p)
{
    int s=0;
    while(p>0)
    {
        s+=v[p];
        p-=(p&(-p));
    }
    return s;
}

int prim(int x)
{
    int z=0, p=(1<<15);
    while(p>0)
    {
        if(z+p<=n && v[z+p]<x)
        {
            z+=p;
            x-=v[z];
        }
        p/= 2;
    }
    return z+1;
}

int main()
{
    int x=1, p, r, a;
    ci >> n;
    for(int i=1; i<=n; i++)
    {
        update(i,1);
    }
    for(int j=1; j<=n; j++)
    {
        a=j%(n-j+1);
        if (a==0)
        {
            a=n-j+1;
        }
        p=suma(n);
        r=suma(x);
        if(p-r>=a)
        {
            x=prim(r+a);
        }
        else
        {
            x=prim(r-p+a);
        }
        co << x << " ";
        update(x,-1);
    }
    return 0;
}