Cod sursa(job #3241634)

Utilizator SSKMFSS KMF SSKMF Data 1 septembrie 2024 17:00:46
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
using namespace std;

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

int arbore[30001];

inline void Update (int indice , const int limita)
{
    for ( ; indice <= limita ; indice += (indice & -indice))
        { arbore[indice]++; }
}

inline int Query (int indice)
{
    int __suma = 0;
    for ( ; indice ; indice ^= (indice & -indice))
        { __suma += arbore[indice]; }

    return __suma;
}

int main ()
{
    int lungime;
    cin >> lungime;

    for (int indice = 1 , actual = 1 ; indice <= lungime ; indice++)
    {
        int termen = (indice - 1) % (lungime - indice + 1) + 1;
        const int ramas = lungime - indice + 1 - (actual - Query(actual));
        if (ramas < termen) { termen -= ramas; }
        else { termen += lungime - indice + 1 - ramas; }
    
        actual = 0;
        for (int putere = (1 << 14) ; putere ; putere >>= 1) {
            if ((actual | putere) <= lungime && putere - arbore[actual | putere] < termen)
                { termen -= putere - arbore[actual |= putere]; }
        }

        cout << ++actual << ' ';

        Update(actual , lungime);
    }

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