Cod sursa(job #2904084)

Utilizator AnaVoineaVoinea Ana Maria AnaVoinea Data 17 mai 2022 22:11:54
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream f("order.in");
ofstream g("order.out");

int a[400001];
void creaza_arb (int nod, int l, int r )
{

    if(l == r)
    {
        a[nod]=1;
        return;
    }
    int m =(l+r)/2;
    creaza_arb(2*nod, l, m);
    creaza_arb (2*nod+1, m+1, r);

    a[nod] = a[2*nod] + a[2*nod+1];
}
int cautare(int nod, int l, int r, int poz)
{
    if( l == r) return l;

    int m=(l+r)>>1;
    if(a[2*nod] < poz) return cautare(2*nod+1, m+1, r, poz-a[2*nod]);
    else return cautare(2*nod, l, m, poz);
}
void modifica(int nod, int l, int r, int x)
{
    if (l == r)
    {
        a[nod] = 0;
        return;
    }

    int m=(l+r)/2;
    if (x <= m) modifica(2*nod, l, m, x);
    else modifica(2*nod+1, m+1, r, x);

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

int main()
{
    int n;
    f>>n;
    creaza_arb(1,1,n);

    int poz =2;
    for( int i=1; i<=n; i++)
    {
        poz += i-1;
        while(poz>a[1])
            poz -= a[1];

        int c = cautare(1, 1, n, poz);
        g<<c<<" ";
        modifica(1,1,n,c);
    }

    return 0;
}