Pagini recente » Cod sursa (job #140117) | Cod sursa (job #961337) | Cod sursa (job #2351570) | Cod sursa (job #2354776) | Cod sursa (job #2777128)
#include <fstream>
using namespace std;
int n;
ifstream cin("order.in");
ofstream cout("order.out");
const int NMAX = 30005;
int aib[NMAX];
void update(int poz, int val){
for(int i = poz; i <= n; i += i & (-i))
aib[i] += val;
}
int querry(int val){
int sum = 0;
for(int i = val; i > 0; i -= i & (-i))
sum += aib[i];
return sum;
}
int CautareBinara(int val){
int sol = n;
int st = 1, dr = n;
while(st <= dr){
int mij = st + dr;
mij/= 2;
if(querry(mij) <= val){
sol = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
return sol;
}
int find_min(int sol, int poz){///caut copilul care trebuie scos
while(querry(sol) == poz)
sol--;
sol++;
return sol;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
update(i, 1);
int poz = 2;
for(int i = 1; i <= n; i ++){
poz = (poz + i - 1) % (n - i + 1);/// al catelea copil ramas in sir trebuie sa scoatem
if(poz == 0)
poz = n - i + 1;
int sol = CautareBinara(poz);
sol = find_min(sol, poz);
update(sol, -1);
cout << sol << " ";
}
return 0;
}