Pagini recente » Cod sursa (job #1372846) | Cod sursa (job #2962991) | Cod sursa (job #1358570) | Cod sursa (job #3141506) | Cod sursa (job #2753361)
#include <iostream>
using namespace std;
int v[100000], indexVal;
void construieste(int pozNod, int indexSt, int indexDr) {
if (indexSt == indexDr) {
v[pozNod] = 1;
return;
}
int indexMij = (indexSt + indexDr) / 2;
if (indexVal <= indexMij) {
construieste(2 * pozNod, indexSt, indexMij);
} else {
construieste(2 * pozNod + 1, indexMij + 1, indexDr);
}
v[pozNod] = v[2 * pozNod] + v[2 * pozNod + 1];
}
void afiseazaSiStergeElementulNumarulK(int pozNod, int indexSt, int indexDr, int k) {
if (indexSt == indexDr) {
// Afiseaza
cout << indexSt << " ";
// Sterge elementul
v[pozNod] = 0;
return;
}
int indexMij = (indexSt + indexDr) / 2;
if (k <= v[2 * pozNod]) {
// Ne intereseaza al K-lea element. Sunt cel putin K elemente in subarborele stang. Mergem in stanga.
afiseazaSiStergeElementulNumarulK(2 * pozNod, indexSt, indexMij, k);
} else {
// Ne intereseaza al K-lea element. Nu sunt K element in subarborele stang, deci trebuie sa mergem
// in cel drept. Totusi, in cel drept ne va interesa al K - [nr elemente in intervalul stang] elemente.
afiseazaSiStergeElementulNumarulK(2 * pozNod + 1, indexMij + 1, indexDr, k - v[2 * pozNod]);
}
// Fiii sigur au fost actualizati (din moment ce o frunza a fost actualizata), deci trebuie actualizat si
// nodul curent
v[pozNod] = v[2 * pozNod] + v[2 * pozNod + 1];
}
int main() {
freopen("order.in", "r", stdin);
freopen("order.out", "w", stdout);
int n;
cin >> n;
for (indexVal = 1; indexVal <= n; indexVal++) {
construieste(1, 1, n);
}
int deSters = 2, copiiRamasi = n;
// Sunt n copii de eliminat
for (int i = 1; i <= n; i++) {
afiseazaSiStergeElementulNumarulK(1, 1, n, deSters);
copiiRamasi--;
if (copiiRamasi) {
deSters = (deSters + i) % copiiRamasi;
// Copiii sunt indexati de la 1. Daca nu pun asta, se va incerca eliminarea copilului 0 (care nici
// macar nu exista) in loc de eliminarea copilului n.
if (deSters == 0) {
deSters = copiiRamasi;
}
} else {
break;
}
}
}