Cod sursa(job #3267129)

Utilizator Luca_georgescuLucageorgescu Luca_georgescu Data 11 ianuarie 2025 09:52:48
Problema Order Scor 100
Compilator cpp-64 Status done
Runda cex_6 Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("order.in");
ofstream g("order.out");

int n,a[30005];
int aib[30005],sol[30005];

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

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

int cb(int val)
{
    int st=1,dr=n;
    int poz=-1;
    while ( st<=dr )
    {
        int m=(st+dr)/2;
        if ( query(m)==val )
        {
            poz=m;
            dr=m-1;
        }
        else if ( query(m)<val )
            st=m+1;
        else
            dr=m-1;
    }
    return poz;
}

int main()
{
    f >> n;
    for (int i=1; i<=n; i++ )
        update(i,1);
    int step=2;
    int mod=n;
    for (int i=1; i<=n; i++ )
    {
        step=(step+i-1)%mod;
        if ( step==0 )
            step=mod;
        mod--;
        int poz=cb(step);
        g << poz << " ";
        update(poz,-1);
    }
    return 0;
}