Cod sursa(job #2019669)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 8 septembrie 2017 12:02:42
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <climits>
#define ub(haha) (haha & (-haha))
using namespace std;

ifstream f ("order.in");
ofstream g ("order.out");

int N, NX, poz, AIB[30003];
void add(int poz, int val) {
    for(int i = poz; i <= N; i += ub(i)) AIB[i] += val;
}

int sum(int poz) {
    int s = 0;
    for(int i = poz; i >= 1; i -= ub(i)) s += AIB[i];
    return s;
}

int bsearch(int val) {
    int st = 1, dr = N, mij = 0, nr = 0, MIN = INT_MAX;
    while(st <= dr) {
        mij = (st + dr) / 2;
        nr = sum(mij);
        if(nr == val && mij < MIN) MIN = mij;
        else if (nr < val) st = mij + 1;
             else dr = mij - 1;
    }
    return MIN;
}

int main() {
    f >> N;
    for(int i = 1; i <= N; i++) add(i, 1);
    NX = N, poz = 2;
    for(int i = 1; i <= N; i++) {
        int x = bsearch(poz);
        add(x, -1);
        g << x << " ";
        NX--;
        poz += i;
        if(NX) poz = ((poz % NX == 0)? NX : poz % NX);
    }
    g << "\n";
    return 0;
}