Cod sursa(job #2616026)

Utilizator As932Stanciu Andreea As932 Data 16 mai 2020 14:39:54
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>

using namespace std;

ifstream cin("order.in");
ofstream cout("order.out");

const int nmax=30005;

int n,aib[nmax];

void update(int poz,int val)
{
    for(;poz<=n;poz+= poz & -poz)
        aib[poz]+=val;
}

int query(int poz)
{
    int sum=0;
    for(;poz>0;poz-= poz & -poz)
        sum+=aib[poz];
    return sum;
}

int main()
{
    cin>>n;

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

    int rest=n,rm=1;
    for(int i=1;i<=n;i++)
    {
        rm+=(i-1);

        rm%=rest;

        int st=1,dr=n,ans=0;

        while(st<=dr)
        {
            int mij=(st+dr)/2;

            if(query(mij)<rm+1)
                st=mij+1;
            else
            {
                ans=mij;
                dr=mij-1;
            }
        }

        cout<<ans<<" ";

        update(ans,-1);
        --rest;
    }

    return 0;
}