Cod sursa(job #2736361)

Utilizator Catalinu23Gavrila Catalin Catalinu23 Data 3 aprilie 2021 13:22:26
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;

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

int n;
int aint[200005];

void Update(int nod, int st, int dr, int poz)
{
    if(st==dr)
    {
        aint[nod]=0;
        return;
    }
    int mij=(st+dr)/2;
    if(poz <= mij)
        Update(nod*2, st, mij ,poz);
    else
        Update(nod*2+1, mij+1, dr, poz);
    aint[nod]=aint[nod*2]+aint[nod*2+1];
}

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

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

int main()
{
    fin>>n;
    Build(1, 1, n);
    int poz=2;
    for(int i=1; i<=n; i++)
    {
        poz+=(i-1);
        poz%=aint[1];
        int q=Query(1,1,n,poz);
        fout<<q<<" ";
        Update(1,1,n,q);
    }
    return 0;
}