Cod sursa(job #3260231)

Utilizator RazvanVelcuVelcu Razvan RazvanVelcu Data 1 decembrie 2024 08:41:00
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
#define bit(x) (x & (-x))

using namespace std;

const int NMAX = 30000;
int aib[NMAX + 1];
int n;

void update(int pos, int val) {
    for(int i = pos; i <= n; i += bit(i)) {
        aib[i] += val;
    }
}

int query(int pos) {
    int s = 0;
    for(int i = pos; i >= 1; i -= bit(i)) {
        s += aib[i];
    }
    return s;
}

int main() {
    ifstream f("order.in");
    ofstream g("order.out");
    f >> n;
    for(int i = 1; i <= n; i++) {
        update(i, 1);
    }
    int pos = 2;
    int cnt = n;
    for(int i = 1; i <= n; i++) {
        pos = (pos + i - 1) % cnt;
        if(pos == 0) {
            pos = cnt;
        }
        cnt--;
        int st = 1;
        int dr = n;
        int sol = 0;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(query(mid) >= pos) {
                sol = mid;
                dr = mid - 1;
            } else {
                st = mid + 1;
            }
        }
        g << sol << ' ';
        update(sol, -1);
    }
    return 0;
}