Cod sursa(job #2752512)

Utilizator As932Stanciu Andreea As932 Data 18 mai 2021 10:42:27
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>

using namespace std;

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

const int nmax = 1e5 + 5;

int n, arb[nmax];

void build(int nod, int st, int dr){
    if(st == dr){
        arb[nod] = 1;
        return;
    }

    int mid = (st + dr) / 2;
    build(nod * 2, st, mid);
    build(nod * 2 + 1, mid + 1, dr);
    arb[nod] = arb[nod * 2] + arb[nod * 2 + 1];
}

void update(int nod, int st, int dr, int pos){
    if(st == dr){
        arb[nod] = 0;
        return;
    }

    int mid = (st + dr) / 2;
    if(pos <= mid)
        update(nod * 2, st, mid, pos);
    else
        update(nod * 2 + 1, mid + 1, dr, pos);

    arb[nod] = arb[nod * 2] + arb[nod * 2 + 1];
}

int query(int nod, int st, int dr, int val){
    if(st == dr)
        return st;

    int mid = (st + dr) / 2;
    if(val <= arb[nod * 2])
        return query(nod * 2, st, mid, val);
    else
        return query(nod * 2 + 1, mid + 1, dr, val - arb[nod * 2]);
}

void solve(){
    int pos = 2;

    for(int i = 1; i <= n; i++){
        pos += (i - 1);

        while(pos > arb[1])
            pos -= arb[1];

        int rsp = query(1, 1, n, pos);
        fout << rsp << " ";

        update(1, 1, n, rsp);
    }
}

int main()
{
    fin >> n;
    build(1, 1, n);
    solve();

    return 0;
}