Cod sursa(job #3224263)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 15 aprilie 2024 00:22:35
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");

const int nmax = 30005;

int a[5 * nmax];
int n, p, k;

void build(int nod, int st, int dr) {
    if ( st == dr ) {
        a[nod] = 1;
        return;
    }
    int mij = ( st + dr ) / 2;
    build(2 * nod, st, mij);
    build(2 * nod + 1, mij + 1, dr);
    a[nod] = a[2 * nod] + a[2 * nod + 1];
}

void update(int nod, int st, int dr, int l, int x) {
    if ( st == dr ) {
        a[nod] = x;
        return;
    }
    int mij = ( st + dr ) / 2;
    if ( l <= mij )
        update(2 * nod, st, mij, l, x);
    else
        update(2 * nod + 1, mij + 1, dr, l, x);
    a[nod] = a[2 * nod] + a[2 * nod + 1];
}

int query(int nod, int st, int dr, int x) {
    if ( st == dr )
        return st;
    int mij = ( st + dr ) / 2;
    if ( a[2 * nod] >= x )
        return query(2 * nod, st, mij, x);
    else
        return query(2 * nod + 1, mij + 1, dr, x - a[2 * nod]);
}

int sum(int node, int st, int dr, int l, int r) {
    if (l > dr || r < st) {
        return 0;
    }

    if (l >= st && r <= dr) {
        return a[node];
    }

    int m = (l + r) / 2;

    return sum(2 * node, st, dr, l, m) + sum(2 * node + 1, st, dr, m + 1, r);
}

int main()
{
    f >> n;
    build(1, 1, n);
    k = 1;
    for ( int i = 1; i <= n; i++ ) {
        int s = sum(1, 1, k, 1, n);

        int to_add = s + i;
        if (to_add > n - i + 1) {
            to_add %= (n - i + 1);
            if (to_add == 0) {
                to_add = n - i + 1;
            }
        }
        k = query(1, 1, n, to_add);
        g << k << " ";
        update(1, 1, n, k, 0);
    }
    g << '\n';
    f.close();
    g.close();
    return 0;
}