Cod sursa(job #3149116)

Utilizator dragutamihai1234Draguta Mihai dragutamihai1234 Data 6 septembrie 2023 14:40:54
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 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 main()
{
    f >> n;
    build(1, 1, n);
    k = 1;
    for ( int i = 1; i <= n; i++ ) {
        k = ( k + i - 1 ) % a[1] + 1;
        p = query(1, 1, n, k);
        update(1, 1, n, p, 0);
        k--;
        g << p << ' ';
    }
    g << '\n';
    f.close();
    g.close();
    return 0;
}