Cod sursa(job #3320765)

Utilizator Alex21Ungureanu Alexandru Alex21 Data 7 noiembrie 2025 11:24:39
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
using namespace std;

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

#define MAX 30005
int n, AIB[MAX];

void gen_AIB() {
    fin >> n;

    for (int bitmask = 1; bitmask <= n; bitmask *= 2) {
        for (int i = bitmask; i <= n; i += 2 * bitmask) {
            for (int j = i - 1; j > i - bitmask; j -= j & (-j)) {
                AIB[i] += AIB[j];
            }

            AIB[i]++;
        }
    }
}

void update(int poz, int val) {
    for (int i = poz; i <= n; i += i & (-i)) {
        AIB[i] += val;
    }
}

int query_sum(int poz) {
    int sum = 0;

    for (int i = poz; i > 0; i -= i & (-i)) {
        sum += AIB[i];
    }

    return sum;
}

int cb(int val) {
    int ans = 0;

    for (int bm = 1 << 15; bm > 0; bm /= 2) {
        if (ans + bm <= n && query_sum(ans + bm - 1) < val) {
            ans += bm;
        }
    }

    return ans;
}

int main() {
    gen_AIB();
    int remaining = n;
    int last_killed = 1;
    int i = 1;

    while (remaining) {
        int next_killed = 0;
        
        if (remaining == 1) {
            next_killed = cb(1);
        } else {
            int left_before_lk = query_sum(last_killed);
            int j = remaining - left_before_lk;

            if (j >= i) {
                next_killed = cb(left_before_lk + i);
            } else {
                next_killed = cb((i - j) % remaining);
            }
        }

        fout << next_killed << ' ';
        update(next_killed, -1);
        last_killed = next_killed;

        remaining--;
        i++;
    }

    return 0;
}