Cod sursa(job #2262922)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 17 octombrie 2018 22:18:52
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>

using namespace std;

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

int N, pow = 1;
int aib[30005];

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

void Update(int pos, int val)
{
    for(int i = pos; i <= N; i += LastBit(i))
        aib[i] += val;
}

int Query(int pos)
{
    int answer = 0;

    for(int i = pos; i > 0; i -= LastBit(i))
        answer += aib[i];

    return answer;
}

int Search(int val)
{
    int cursor = 0;

    for(int step = pow; step > 0; step >>= 1)
        if(cursor + step < N && aib[cursor + step] < val)
        {
            cursor += step;
            val -= aib[cursor];
        }

    return cursor + 1;
}

int main()
{
    fin >> N;

    for(; pow <= N; pow <<= 1);

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

    fout << 2 << ' ';
    Update(2, -1);
    int currentPos = 2;

    for(int i = 2; i <= N; i++)
    {
        int realSteps = i % Query(N);
        int posRight = Query(N) - Query(currentPos);
        int posLeft = Query(currentPos);
        int elimPos;

        if(realSteps == 0)
            realSteps = N - i + 1;

        if(realSteps > posRight)
            elimPos = Search(realSteps - posRight);
        else
            elimPos = Search(realSteps + posLeft);

        fout << elimPos << ' ';
        Update(elimPos, -1);
        currentPos = elimPos;
    }

    return 0;
}