Cod sursa(job #1806331)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 15 noiembrie 2016 09:44:11
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <climits>
#define ub(haha) (haha & (-haha))
using namespace std;

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

int N, poz, inv, x, AIB[30001];
int add(int poz, int val) {
    for(int i = poz; i <= N; i += ub(i)) AIB[i] += val;
    return 0;
}

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

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

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