Cod sursa(job #3157437)

Utilizator SSKMFSS KMF SSKMF Data 15 octombrie 2023 15:56:55
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
using namespace std;

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

int lungime , eliminat[30001];

void Update (int indice)
{
    while (indice <= lungime)
        { eliminat[indice]++; indice += (indice & -indice); }
}

int Suma (int indice)
{
    int suma = 0;
    while (indice)
        { suma += eliminat[indice]; indice -= (indice & -indice); }

    return suma;
}

int Ordine_Ramas (const int indice)
{
    int pozitie = 0;
    for (int salt = (1 << 16) ; salt ; salt >>= 1)
        if (pozitie + salt <= lungime && (pozitie + salt) - Suma(pozitie + salt) < indice)
            pozitie += salt;

    return pozitie + 1;
}

int main ()
{
    cin >> lungime;

    for (int indice = 1 , inceput = 1 ; indice <= lungime ; indice++)
    {
        const int eliminare = Ordine_Ramas((indice + inceput - Suma(inceput) - 1) % (lungime - indice + 1) + 1);
        Update(inceput = eliminare); cout << eliminare << '\n';
    }

    cout.close(); cin.close();
    return 0;
}