Cod sursa(job #3229161)

Utilizator Sebi_RipaSebastian Ripa Sebi_Ripa Data 14 mai 2024 09:45:03
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>

using namespace std;

int st[120000];
int n;

void update(int l, int r, int node, int poz, int val) {
    if(l == r) {
        st[node] = val;
        return;
    }
    int mid = (l+r)/2;
    if(poz <= mid) update(l, mid, node*2, poz, val);
    else update(mid+1, r, node*2+1, poz, val);
    st[node] = st[2*node] + st[2*node+1];
}

int query(int l, int r, int node, int ql, int qr) {
    if(ql <= l && r <= qr)
        return st[node];
    int mid = (l+r)/2, s = 0;
    if(mid >= ql) s += query(l, mid, node*2, ql, qr);
    if(qr >= mid+1) s += query(mid+1, r, node*2+1, ql, qr);
    return s;
}

int cb(int l, int r, int val) {
    int sol = -1;
    while(l <= r) {
        int mid = (l+r)/2;
        if(query(1, n, 1, 1, mid) >= val)
            r = mid-1, sol = mid;
        else l = mid+1;
    }
    if(sol == -1)
        sol = l;
    return sol;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        update(1, n, 1, i, 1);
    int poz = 1;
    for(int i = 1; i <= n; i++) {
        int poz1 = (i%(n-i+1) + query(1, n, 1, 1, poz))%(n-i+1);
        if(poz1 == 0)
            poz1 = (n-i+1);
        poz= cb(1, n, poz1);
        cout << poz << ' ';
        update(1, n, 1, poz, -1);
    }
}