Cod sursa(job #2439905)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 17 iulie 2019 11:00:32
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>

using namespace std;

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

const int NMAX = 3e4 + 5;

int N, AIB[NMAX], pos, M, ans;

inline int UB (int X)
{
    return (X & (-X));
}

inline void Update (int poz, int val)
{
    for(int i = poz; i <= N; i += UB(i))
        AIB[i] += val;

    return;
}

inline int Query (int poz)
{
    int ans = 0;

    for(int i = poz; i >= 1; i -= UB(i))
        ans += AIB[i];

    return ans;
}

inline int CB (int X)
{
    int Left = 1, Right = N, rasp = 0;

    while(Left <= Right)
    {
        int Mid = (Left + Right) / 2;

        if(Query(Mid) < X)
        {
            rasp = Mid;

            Left = Mid + 1;
        }
        else
            Right = Mid - 1;
    }

    ++rasp;

    return rasp;
}

int main()
{
    f.tie(NULL);

    f >> N;

    for(int i = 1; i <= N; ++i)
        Update(i, 1);

    pos = 2;

    M = N;

    for(int i = 1; i <= N; ++i)
    {
        pos = (pos + i - 1) % M;
        if(pos == 0)
            pos = 1;

        ans = CB(pos);

        g << ans << ' ';

        Update(ans, -1);
        --M;
    }

    return 0;
}