Cod sursa(job #2757203)

Utilizator alessiamtr12Mitrica Alessia alessiamtr12 Data 4 iunie 2021 15:14:39
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>

using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n,aib[30005];
int lsb(int x)
{
    return x&(-x);
}
int x;
void update(int val,int k)
{
    for(int i=k;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int query(int k)
{
    int sum=0;
    while(k)
    {
        sum+=aib[k];
        k-=lsb(k);
    }
    return sum;
}
void cauta()
{
    int poz=2,st,dr,sol,mid;
    for(int i=1;i<=n;i++)
    {
        poz=(poz+i-1)%(n-i+1);
        if(poz==0)
            poz=n-i+1;
        st=1;
        dr=n;
        sol=n;
        while(st<=dr)
        {
             mid=(st+dr)/2;
             if(query(mid)<=poz)
             {
               sol=mid;
               st=mid+1;
             }
             else
                dr=mid-1;
        }
        while(query(sol)==poz)
            sol--;
        sol++;
        update(-1,sol);
        fout<<sol<<" ";
    }
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        update(1,i);
    }
    cauta();
    return 0;
}