Pagini recente » Cod sursa (job #3259980) | Cod sursa (job #1618213) | Cod sursa (job #2350336) | Cod sursa (job #1479221) | Cod sursa (job #3321552)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
struct copil {
int scos, val;//scos verifica daca a fost scos sau nu un element
//Daca e un element e doar 0/1
//iar val este nr copliului la inceput
};
vector<int>aib;
vector<int>aux;
int lsb(int n) {
return n & (-n);
}
void updateScos(int add, int poz) {
for (int i = poz; i < aib.size(); i += lsb(i)) {
aib[i] += add;
}
}
int query(int poz) {
int sum = 0;
for (int i = poz; i > 0; i -= lsb(i)) {
sum += aib[i];
}
return sum;
}
int cb(int elemFind) {
int elemCrt = 0;
int sumant = 0;
for (int i = (1<<17); i > 0; i/=2)
{
if (i + elemCrt < aib.size() && sumant + aib[i + elemCrt] < elemFind) {
sumant += aib[i + elemCrt];
elemCrt += i;
}
}
return elemCrt+1;
}
vector<int>v;
int main()
{
int tests;
fin >> tests;
int nrCopchii=tests;
int valant = 1;
int pozNextKid=0;
aib.resize(2* tests + 1);
aux.resize(2 * tests + 1);
//Construim aib in care punem daca un copil e scos sau nu
for (int i = 1; i <= nrCopchii; ++i) {
updateScos(1, i);
}
int totalCopiiAux = tests;
for (int i = 0; i < tests; ++i) {
valant += i;
valant %= totalCopiiAux;
//We do that cause if it's 1 than the previous kid will be 0 and that is wrong
++valant;
pozNextKid=cb(valant);//the kid we wanna kill :D
//We erase a kid from the AIB
updateScos(-1,pozNextKid);
fout << pozNextKid << " ";
valant--;
totalCopiiAux--;//Cause we erased one child
}
return 0;
}
//=^..^=