Mai intai trebuie sa te autentifici.
Cod sursa(job #2753359)
Utilizator | Data | 22 mai 2021 16:33:17 | |
---|---|---|---|
Problema | Order | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.61 kb |
#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]) {
afiseazaSiStergeElementulNumarulK(2 * pozNod, indexSt, indexMij, k);
} else {
afiseazaSiStergeElementulNumarulK(2 * pozNod + 1, indexMij + 1, indexDr, k - v[2 * pozNod]);
}
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;
if (deSters == 0) {
deSters = copiiRamasi;
}
} else {
break;
}
}
}