Pagini recente » Cod sursa (job #848141) | Cod sursa (job #1344574) | Cod sursa (job #463054) | Cod sursa (job #2307680) | Cod sursa (job #1253472)
#include <fstream>
using namespace std;
int arb[1000000], n;
void build_arb (int i, int st, int dr)
{
int m = (st+dr)/2;
if (st!=dr)
{
build_arb (i*2, st, m);
build_arb (i*2+1, m+1, dr);
arb[i] = arb[i*2] + arb[i*2+1];
}
else
{
arb[i] = 1;
}
}
int query (int st, int dr, int i, int el)
{
int m = (st+dr)/2;
if (st==dr)
return st;
if (el > arb[i*2])
return query (m+1, dr, i*2+1, el-arb[i*2]);
else
return query (st, m, i*2, el);
}
void update (int st, int dr, int i, int poz)
{
int m = (st+dr)/2;
if (st==dr)
{
arb[i] = 0;
return;
}
if (poz <= m)
update (st, m, i*2, poz);
else
update (m+1, dr, i*2+1, poz);
arb[i] = arb[i*2] + arb[i*2+1];
}
int main ()
{
ifstream in ("order.in");
ofstream out ("order.out");
in>>n;
build_arb (1, 1, n);
int r = n, i=2, nr=1, el;
while (r)
{
i = (i+nr-1)%r;
if(i==0)
i=r;
el = query (1, n, 1, i);
out<<el<<" ";
update (1, n, 1, el);
r--;
nr++;
}
return 0;
}