Cod sursa(job #3321552)

Utilizator nicoleta_iancuIancu Nicoleta nicoleta_iancu Data 10 noiembrie 2025 08:55:33
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb

#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;
}
//=^..^=