Cod sursa(job #3152274)

Utilizator adelinapetreAdelina Petre adelinapetre Data 24 septembrie 2023 15:04:29
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("order.in");
ofstream cout("order.out");
int bit[1000005];
int n;
void update(int i, int val)
{
    while(i<=n)
    {
        bit[i]+=val;
        i+=i&(-i);
    }
}
int prefix(int i)
{
    int sum=0;
    while(i>0)
    {
        sum+=bit[i];
        i-=i&(-i);
    }
    return sum;
}
int lb(int st, int dr, int a)
{
    int mid,sol=n;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(prefix(mid)>=a)
            sol=mid, dr=mid;
        else
            st=mid+1;
    }
    return sol;
}
int main()
{
    int i,cnt=1,poz=0,aux=2;
    cin>>n;
    for(i=1; i<=n; i++)
        update(i,1);
    i=1;
    while(cnt<=n)///cat timp mai am numere;
    {
        aux=(aux+n-1)%(n-i+1)+1;
        poz=lb(0,n,aux);
        ///cout<<lb(1,n,aux)<<" ";
        cout<<poz<<" ";
       // cout<<cnt<<'\n';
        cnt++; i++;
        update(poz,-1);
    }
    return 0;
}