Cod sursa(job #3261665)

Utilizator nokih53838Noki H nokih53838 Data 7 decembrie 2024 10:47:03
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <set>
using namespace std;

const int N = 30005;
int n, aib[N], remaining;
set<int> active;

inline void Update(int pos, int val) {
    for (int i = pos; i <= n; i += i & -i)
        aib[i] += val;
}

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

inline int Find(int pos) {
    auto it = active.lower_bound(pos);
    if (it == active.end())
        it = active.begin();
    return *it;
}

inline int Next(int pos, int step) {
    step %= remaining;
    if (step == 0) step = remaining;

    int queryPos = Query(pos - 1);
    int target = queryPos + step;

    int left = 1, right = n, result = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (Query(mid) >= target) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return Find(result);
}

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

    fin >> n;

    for (int i = 1; i <= n; ++i) {
        Update(i, 1);
        active.insert(i);
    }
    remaining = n;

    int pos = 1;
    for (int step = 1; step <= n; ++step) {
        pos = Next(pos, step);
        --remaining;
        Update(pos, -1);
        active.erase(pos);
        fout << pos << ' ';
    }

    fin.close();
    fout.close();
    return 0;
}