Cod sursa(job #3152605)

Utilizator Sebi_RipaSebastian Ripa Sebi_Ripa Data 25 septembrie 2023 21:07:16
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> bits(30005, 0);
int n;

void update(int i, int val) {
    while(i <= n) {
        bits[i] += val;
        i += (i&-i);
    }
}

int presum(int i) {
    int sum = 0;
    while(i > 0) {
        sum += bits[i];
        i -= (i&-i);
    }
    return sum;
}

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

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        update(i, 1);
    int poz1 = 2;
    for(int i = 1; i <= n; i++) {
        poz1 = (poz1 +  n - 1)%(n - i + 1) + 1;
        int poz = cb(1, n, poz1);
        fout << poz << ' ';
        update(poz, -1);
    }
    return 0;
}