Cod sursa(job #2290833)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 27 noiembrie 2018 02:23:04
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>

#define Zeros(X) X&(-X)
#define MAXN     30005

int N;
int AIB[MAXN];

inline void Update(int X, int Value) {
    for (; X<=N; X +=   Zeros(X))
        AIB[X] += Value;
}

inline int Query(int X) {
    int Sum = 0;
    for (; X; X -= Zeros(X))
        Sum += AIB[X];
    return Sum;
}

int Search(int Left, int Right, int Value) {
    int L = Left-1, R = N+1, Mid;
    while (Left <= Right) {
        Mid = (Left+Right)/2;
        if (Query(Mid) - Query(L) >= Value)
            R = std::min(R, Mid), Right = Mid-1;
        else Left = Mid+1;
    }   return R;
}

std::ifstream In("order.in");
std::ofstream Out("order.out");

void Citire() {
    In >> N;
}

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

    #define _Ramase (N-i+1)

    for (int i=1, Last = 2, Sum, Left, Right, p; i<=N; ++i) {
        Sum = Query(N) - Query(Last-1);
        p = 1 + (i-1) % _Ramase;

        if (Sum < p)
            p -= Sum,
            Left = 1, Right = Last;
        else
            Left = Last, Right = N;

        Out << (Last = Search(Left, Right, p)) << ' ' ;
        Update(Last, -1);
    }
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}