Cod sursa(job #2954412)

Utilizator Pop_EmilPal Tamas Pop_Emil Data 14 decembrie 2022 10:35:52
Problema Order Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>

using namespace std;

int N;
int BIT[30005];
FILE *in = fopen("order.in", "r"), *out = fopen("order.out", "w");

void update(int pos, int val){
    for (int i = pos; i <= N; i += i & (-i))
        BIT[i] += val;
}

int query(int pos){
    int sum = 0;
    for (int i = pos; i >= 1; i -= i & (-i))
        sum += BIT[i];
    return sum;
}

int BS(int val){

    int k, L = 1, R = N, M, S;
    while (L <= R) {
        M = (L + R) / 2;
        S = query(M);
        if (S < val)
            L = M + 1;
        else if (S > val)
            R = M - 1;
        else {
            k = M;
            while(query(k-1) == val && k > 0)
                --k;
            break;
        }
    }
    return k;
}

int main()
{
    fscanf(in, "%d", &N);
    // Initialize BIT (BIT[i] = nr of not eliminated children in appropriate interval)
    for (int i = 1; i <= N; ++i)
        update(i, 1);

    int L = N, steps, pos = 1, preL;
    for (int i = 1; i <= N; ++i){
        if (L > 1)
            steps = i % L;
        else
            steps = 1;
        preL = query(pos);
        //
        if (preL + steps > L) {
            pos = BS(1);
            steps -= L - preL + 1;
            preL = query(pos);
        }
        //
        pos = BS(preL + steps);
        fprintf(out, "%d ", pos);
        update(pos, -1);
        L -= 1;
    }

    return 0;
}