Cod sursa(job #3320311)

Utilizator Lex._.Lex Guiman Lex._. Data 4 noiembrie 2025 21:31:43
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
#define NMAX 30001
using namespace std;

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

int aib[NMAX];

int query(int nr, int n) ///cautam a nr-a pozitie libera
{
    int putere2=1;
    while((putere2<<1)<=n) putere2<<=1;
    int suma=0, poz=0;
    while(putere2>0)
    {
        if(poz+putere2<=n && suma+putere2-aib[poz+putere2]<nr)
        {
            suma+=putere2-aib[poz+putere2];
            poz+=putere2;
        }
        putere2>>=1;
    }
    return poz+1;
}

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

int main()
{
    int n;
    in >> n;
    int indice_copil=1;
    for(int i=1; i<=n; i++)
    {
        int nr_copii=n-i+1;
        indice_copil+=i;

        indice_copil=indice_copil%nr_copii;
        if(indice_copil==0) indice_copil+=nr_copii;

        int poz=query(indice_copil, n);
        out << poz << " ";
        update(poz, n);

        indice_copil--;
    }

    return 0;
}