Cod sursa(job #1810150)

Utilizator OFY4Ahmed Hamza Aydin OFY4 Data 19 noiembrie 2016 17:35:43
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>

using namespace std;

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

const int Max = 30010;
int aib[Max], n, meh;

void aibUpdate(int i, int s)
{
    for(; i <= n; i+= i & (-i))
        aib[i]+= s;
}

int aibQuery(int i)
{
    int s = 0;
    for(;i >= 1; i-= i & (-i))
        s+= aib[i];

    return s;
}

int cautBin(int nr)
{
    int poz = 0;
    for(int i = meh; i >= 0; --i)
    {
        if((poz + (1 << i)) <= n && aib[poz + (1 << i)] < nr)
        {
            poz+= 1 << i;
            nr-= aib[poz];
        }
    }

    return poz + 1;
}
int main()
{
    int k = 2, cevap;
    in >> n;
    for(int i = 1; i <= n; ++i)
    {
        aibUpdate(i,1);
    }
    for(meh = 1; (1 << meh) <= n; ++meh);
    --meh;

    for(int i = 2; i <= n; ++i)
    {
        cevap = cautBin(k);
        aibUpdate(cevap, -1);
        out << cevap << " ";

        k = (k - 1+ i) % (n - i + 1);
        if(k == 0)
            k = n - i + 1;
    }
    cevap = cautBin(k);
    out << cevap << " ";

    return 0;
}