Pagini recente » Istoria paginii utilizator/etgeniuand | Istoria paginii utilizator/saitatter | Istoria paginii utilizator/mariamarinescu | Cod sursa (job #2566469) | Cod sursa (job #2904076)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("mit.in");
ofstream g("mit.out");
int a[4000001];
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;
}