Cod sursa(job #2669750)

Utilizator NanuGrancea Alexandru Nanu Data 7 noiembrie 2020 20:08:31
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("order.in");
ofstream cout("order.out");

#define NMAX 30001
#define Ub(x) (x & (-x))

int aib[NMAX], n, pas, i, nr;

void scad(int pos) {
    for(int i = pos; i <= n; i += Ub(i))
        aib[i]--;
}

int suma(int pos) {
    int i, s = 0;
    for(i = pos; i >= 1; i -= Ub(i))
        s += aib[i];
    return s;
}

int cautBinar(int x) {
    int st = 1, dr = n, pos = NMAX;
    while(st <= dr) {
        int mid = (st + dr) / 2;
        int sum = suma(mid);
        if(sum == x && mid < pos)
            pos = mid;
        else if(x <= sum)
            dr = mid - 1;
        else st = mid + 1;
    }
    return pos;
}

int main() {
    cin >> n;

    for(i = 1; i <= n; i++) //cate pozitii am libere pana la i
        aib[i] = Ub(i);
    
    pas = 2, nr = n;
    for(i = 1; i <= n; i++) {
        int x = cautBinar(pas); //caut cel mai din st indice cu suma egala cu nr de pasi
        cout << x << " " ;
        scad(x);    //scad cati raman pana la fiecare pozitie;

        nr--; //scad nr de copii;
        pas += i;
        if(nr)
            pas %= nr;

        if(pas == 0)
            pas = nr;
        
    }

    return 0;
}