Cod sursa(job #2777810)

Utilizator NeuerRaducu Ioan Stefan Neuer Data 24 septembrie 2021 20:43:02
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>

using namespace std;
const int SIZE = 3e4+10;

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

int n, sind, var;
int arb[SIZE*4];

void formArb(int ind, int st, int dr)
{
    if(st==dr) arb[ind] = 1;
    if(st>=dr) return;
    int mid = (st + dr) / 2;
    formArb(ind*2, st, mid), formArb(ind*2+1, mid+1, dr);
    arb[ind] = arb[ind*2] + arb[ind*2+1];
}

void delnum(int ind, int st, int dr, int num)
{
    if(st==dr) arb[ind] = 0, var = st;
    if(st>=dr) return;
    int mid = (st + dr) / 2;
    if(num<=arb[ind*2]) delnum(ind*2, st, mid, num);
    else delnum(ind*2+1, mid+1, dr, num-arb[ind*2]);
    arb[ind] = arb[ind*2] + arb[ind*2+1];
}

void coutArb(int ind, int st, int dr)
{
    cout<<ind<<": "<<st<<' '<<dr<<" - "<<arb[ind]<<" ;\n";
    if(st>=dr) return;
    int mid = (st + dr) / 2;
    coutArb(ind*2, st, mid), coutArb(ind*2+1, mid+1, dr);
    arb[ind] = arb[ind*2] + arb[ind*2+1];
}

int main()
{
    in>>n;
    formArb(1, 1, n);
    for(int i=1; i<=n; i++)
    {
        sind+=i;
        sind%=arb[1];
        delnum(1, 1, n, sind+1);
        sind--;
        out<<var<<' ';
    }
    return 0;
}