Pagini recente » Cod sursa (job #709991) | Istoria paginii runda/fminostress10simulare/clasament | Profil bombonikdulcik | Cod sursa (job #2105944) | Cod sursa (job #918897)
Cod sursa(job #918897)
#include <iostream>
#include <fstream>
#include <cstdio>
using namespace std;
int n, aib[30010];
inline void Update(int poz, int val)
{
while (poz <= n)
{
aib[poz] += val;
poz = poz + (poz & -poz);
}
}
inline int Query(int poz)
{
int rez = 0;
while (poz)
{
rez = rez + aib[poz];
poz = poz - (poz & -poz);
}
return rez;
}
inline int CautareBinara(int val)
{
int rez, st, dr, mij, x;
st = 1;
dr = n;
while (st <= dr)
{
mij = (st+dr)>>1;
x = Query(mij);
if (x >= val)
{
rez = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
return rez;
}
inline void Read()
{
ifstream f ("order.in");
f>>n;
f.close();
}
inline void Solve()
{
ofstream g ("order.out");
int i;
for (i=1; i<=n; i++)
Update(i, 1); /// pun copiii in aib
int now, next, inc, total;
now = 1;
for (i=1; i<=n; i++)
{
inc = Query(now); /// inc = numarul de copii pe care ii am pana acum, dupa ultima eliminare
total = Query(n); /// total = cati copii mai am in total in momentul de fata
if (total - inc >= i)
{
/// acum trebuie sa elimin al i-lea copil;
/// daca imi ajung copiii pana la final atunci atunci elimin al i-lea copil de unde am ramas
/// adica de la inc
next = inc + i;
}
else
{
/// daca nu am destui copii ca sa il elimin pe al i-lea pana la capat,
/// trebuie sa trec peste cei pe care ii am pana la capat (total - inc)
/// si acum ar trebui sa elimin al (i - (total - inc)) - lea copil pe care la fel nu stiu daca il am
/// pana la capat asa ca fac modulo total.
next = i - (total - inc);
next = next%total;
if (next == 0)
next = total;
}
now = CautareBinara(next); /// caut binar pozitia (cea mai din stanga) unde am al i-lea copil;
g<<now<<" ";
Update(now, -1); /// scot copilul bagat
}
g.close();
}
int main()
{
Read();
Solve();
return 0;
}