Cod sursa(job #2777128)

Utilizator cyg_dragos10Ivan Dragos cyg_dragos10 Data 22 septembrie 2021 11:23:52
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#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;
}