Cod sursa(job #2262424)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 17 octombrie 2018 11:55:54
Problema Order Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>

using namespace std;

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

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

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

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

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

    for(int i = poz; 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);

    int currentPos = 1;
    for(int i = 1; i <= N - 1; i++)
    {
        int realSteps = i % Query(N);
        int posR = Query(N) - Query(currentPos - 1);
        int posL = Query(currentPos);
        int elimPos;

        if(realSteps > posR)
            elimPos = Search(realSteps - posR);
        else
            elimPos = Search(realSteps + posL);

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

    for(int i = 1; i <= N; i++)
        if(!d[i])
        {
            fout << i;
            break;
        }

    return 0;
}