Pagini recente » Cod sursa (job #2364406) | Cod sursa (job #260631) | Cod sursa (job #2009411) | Cod sursa (job #2372336) | Cod sursa (job #1597654)
#include <fstream>
#include <vector>
using namespace std;
ifstream is("order.in");
ofstream os("order.out");
using VI = vector<int>;
int n, beg, elim, poz;
VI a, ok;
void Build(int nod, int st, int dr);
void Update(int nod, int st, int dr);
int Sum(int nod, int st, int dr);
int main()
{
is >> n;
a = VI(4 * n + 1);
ok = VI(n + 1);
Build(1, 1, n);
beg = 1;
for ( int i = 1; i <= n; ++i )
{
poz = beg;
//os << "\nsuma = " << Sum(1, 1, n);
elim = ( Sum(1, 1, n) + i ) % ( n - i + 1);
if ( !elim )
++elim;
//os << "\n" << beg << " " << elim << "!\n";
Update(1, 1, n);
}
is.close();
os.close();
return 0;
}
int Sum(int nod, int st, int dr)
{
if ( st == dr )
return a[nod];
int md = ( st + dr ) / 2;
if ( poz <= md )
return Sum(2 * nod, st, md);
else
return a[2 * nod] + Sum(2 * nod + 1, md + 1, dr);
}
void Update(int nod, int st, int dr)
{
if ( st == dr )
{
a[nod] = 0;
os << st << " ";
ok[st] = 1;
beg = st;
return;
}
int md = ( st + dr ) / 2;
if ( elim <= a[2 * nod] )
Update(2 * nod, st, md);
else
{
elim -= a[2 * nod];
Update(2 * nod + 1, md + 1, dr);
}
a[nod] = a[2 * nod] + a[2 * nod + 1];
}
void Build(int nod, int st, int dr)
{
if ( st == dr )
{
a[nod] = 1;
return;
}
int md = ( st + dr ) / 2;
Build(2 * nod, st, md);
Build(2 * nod + 1, md + 1, dr);
a[nod] = a[2 * nod] + a[2 * nod + 1];
}