Cod sursa(job #3144156)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 5 august 2023 12:33:56
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>

using namespace std;

const int Nmax = 300005;

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

int aint[4 * Nmax];

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

    int mid;
    mid = (st + dr) / 2;

    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);

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

void update(int nod, int st, int dr, int poz){
    if(st == dr){
        fout << st << " ";
        aint[nod] = 0;
        return;
    }

    int mid;

    mid = (st + dr) / 2;

    if(poz <= aint[2 * nod]){
        update(2 * nod, st, mid, poz);
    }
    else{
        update(2 * nod + 1, mid + 1, dr, poz - aint[2 * nod]);
    }

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

int main(){
    int n, poz, len;

    fin >> n;

    build(1, 1, n);

    poz = 1;
    len = n;
    for(int i = 1; i <= n; i++){
        poz += i;

        if(poz > len){
            poz = poz % len;
        }
        if(len == 1){
            poz = 1;
        }

        update(1, 1, n, poz);

        poz--;
        len--;
    }
    return 0;
}