Cod sursa(job #1464521)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 23 iulie 2015 18:41:09
Problema Order Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
using namespace std;
#define Nmax 30001

int n, logN;
int AIB[Nmax];

void update(int, int) ;
int sum(int) ;
int search(int) ;

int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    
    int i, nr, k, poz;
    
    scanf("%d", &n);
    
    for(i = 1; i <= n; ++i) update(i, 1);
    
    for(logN = 0; (1 << logN) < n; ++logN) ;
    
    for(poz = i = 1; i <= n; ++i)
    {
        nr = i % (n + 1 - i);
        if(nr == 0) nr = n + 1 - i;
        
        k = n + 1 - i - sum(poz);
        
        if(nr <= k) poz = search(n + 1 - i - k + nr);
        else poz = search(nr - k);
        
        update(poz, -1);
        
        printf("%d ", poz);
        fflush(stdout);
    }
    
    return 0;
}

void update(int poz, int val)
{
    for(; poz <= n; poz += poz & (-poz)) AIB[poz] += val;
}


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

int search(int val)
{
    int poz, step, rez;
    
    for(poz = 0, step = (1 << logN), rez = 0; step > 0; step >>= 1)
        if(poz + step <= n)
    {
        if(AIB[poz + step] < val)
        {
            poz += step;
            val -= AIB[poz];
        }
        else if(AIB[poz + step] == val) rez = poz + step;
    }
    
    if(val == 0) rez = poz;
    
    return rez;
}