Cod sursa(job #3320207)

Utilizator Lex._.Lex Guiman Lex._. Data 4 noiembrie 2025 16:00:44
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 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 poz=0, putere2=1;
    while((putere2<<1)<=n) putere2<<=1;
    while(putere2>0)
    {
        if(poz+putere2<=n && putere2-aib[poz+putere2]<=nr)
        {
            poz+=putere2;
        }
        putere2>>=1;
    }
    return poz;
}

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++)
    {
        indice_copil+=i;
        int nr_copii=n-i+1;

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

        cout << nr << " ";
        int poz=query(nr, n);
        out << poz << " ";
        update(poz, n);
    }

    return 0;
}