Cod sursa(job #3271416)

Utilizator Tudor_11Tudor Ioan Calin Tudor_11 Data 26 ianuarie 2025 10:32:13
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n;
int aib[30001];
void update(int i,int val)
{
    while(i<=n)
    {
        aib[i]+=val;
        i+=(i&(-i));
    }
}
int query(int i)
{
    int ans=0;
    while(i>0)
    {
        ans+=aib[i];
        i-=(i&(-i));
    }
    return ans;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++) update(i,1);
    int ramas=n,pos=2;
    for(int i=1;i<=n;i++)
    {
        pos=(pos+i-1)%ramas;
        if(pos==0) pos=ramas;
        ramas--;
        int st=1,dr=n,ans;
        while(st<=dr)
        {
            int mid=(st+dr)/2;
            if(query(mid)>=pos)
            {
                ans=mid;
                dr=mid-1;
            }
            else st=mid+1;
        }
        update(ans,-1);
        fout<<ans<<' ';
    }
    return 0;
}