Cod sursa(job #2396318)

Utilizator eduardcadarCadar Eduard eduardcadar Data 3 aprilie 2019 13:36:04
Problema Order Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int val, n, H[100000], poz;
void update(int n, int l, int r, int p, int v) {
    if (l >= r) {H[n] += v; return; }
    int m = (l + r) >> 1;
    if (p <= m) update(n<<1, l, m, p, v);
    else update((n<<1)|1, m+1, r, p, v);
    H[n] = H[n<<1] + H[(n<<1)|1];
}
void queer(int n, int l, int r, int k) {
    if (H[n] < k) {poz = r; return;}
    int m = (l + r) >> 1;
    if (H[n<<1] >= k) queer(n<<1, l, m, k);
    else queer((n<<1)|1, m + 1, r, k - H[n<<1]);
}
int main()
{
    f >> n;
    for (int i = 1; i <= n; ++i) update(1, 1, n, i, 1);
    val = 2;
    for (int i = 1; i <= n; ++i) {
        val = (val - 2 + i) % (n - i + 1) + 1;
        queer(1,1,n,val);
        update(1, 1, n, poz, -1);
        g << poz << ' ';
    }
    g << '\n';
    return 0;
}