Cod sursa(job #2453305)

Utilizator ezioconnorVlad - Gabriel Iftimescu ezioconnor Data 3 septembrie 2019 13:23:49
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>

using namespace std;

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

int n, m;
int AIB[30001];

inline int zeros(int x)
{
    return x & (-x);
}

inline void update(int poz, int val)
{
    for (int i = poz; i <= n; i += zeros(i))
        AIB[i] += val;
}

inline int query(int poz)
{
    int rez = 0;
    for (int i = poz; i; i -= zeros(i))
        rez += AIB[i];
    return rez;
}

inline int cautBin(int x)
{
    int st = 1, dr = n, rez = 0;
    while (st <= dr)
    {
        int mid = (st + dr) >> 1;
        if (query(mid) < x)
        {
            rez = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }
    return rez + 1;
}

int main()
{
    int poz, rez;
    in >> n;
    for (int i = 1; i <= n; ++i)
        update(i, 1);
    poz = 2;
    m = n;
    for (int i = 1; i <= n; ++i)
    {
        poz = (poz + i - 2) % m + 1;
        rez = cautBin(poz);
        out << rez << " ";
        update(rez, -1);
        --m;
    }
    return 0;
}