Cod sursa(job #1797262)

Utilizator DobosDobos Paul Dobos Data 4 noiembrie 2016 10:18:49
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>

const int NMAX = 30005;

using namespace std;

ifstream fin ("order.in");
ofstream fout ("order.out");

int n,AIB[NMAX];
bitset < NMAX > V;
void update(int poz,int val){
    int C = 0;
    while(poz <= n){
        AIB[poz] += val;
        while(!(poz & (1 << C))) C++;
        poz += (1 << C);
        C++;
    }
}

int query(int poz){
    int C = 0,S = 0;
    while(poz > 0){
        S += AIB[poz];
        while(!(poz & (1 << C))) C++;
        poz -= (1 << C);
        C++;
    }
    return S;
}

int Search(int S){
    int step;
    for(step = 1; step < n; step <<= 1);
    for(int i = 0; step > 0; step >>= 1){
        if(i + step <= n){
            if(S >= AIB[i + step]){
                i += step; S -= AIB[i];
                if(!S){
                    while(V[i] == 0)
                        i--;
                    return i;
                }
            }
        }
    }
    return -1;


}

int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int sum,poz;

    fin >> n;

    for(int i = 1; i <= n; i++){
        update(i,1);
        V[i] = 1;
    }
    for(int i = 1,j = 1; j <= n; j++){
        sum = query(i) + j;
        while(sum != 0){
            poz = Search(sum);
            if(poz == -1)
                sum = sum - n + j - 1;
            else {
                 i = poz;
                 update(i,-1);
                 V[i] = 0;
                 sum = 0;
                 fout << i << " ";
            }
        }
    }

    return 0;
}