Cod sursa(job #3183781)

Utilizator puica2018Puica Andrei puica2018 Data 13 decembrie 2023 10:52:56
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
int aib[30005];

void update(int p,int v)
{
    for(int i=p; i<=n; i+=(i&(-i)))
        aib[i]+=v;
}

int query(int l,int r)
{
    if(l>r)
        return 0;
    int ans=0;
    for(int i=r; i>=1; i-=(i&(-i)))
        ans+=aib[i];
    for(int i=l-1; i>=1; i-=(i&(-i)))
        ans-=aib[i];
    return ans;
}

int f(int a,int b)
{
    if(a%b==0)
        return b;
    return a%b;
}

int main()
{
    fin>>n;

    for(int i=1; i<=n; i++)
        update(i,1);

    int p=1;
    for(int i=1; i<=n; i++)
    {
        int cnt=query(p+1,n);
        int pp=0;
        if(cnt>=i)
        {
            int st=p+1,dr=n,mij;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(query(p+1,mij)>=i)
                {
                    pp=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
        }
        else
        {
            int st=1,dr=n,mij;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(query(1,mij)>=f(i-cnt,n-i+1))
                {
                    pp=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
        }

        p=pp;

        update(p,-1);

        fout<<p<<" ";
    }
    fout<<"\n";
    return 0;
}