Cod sursa(job #1611971)

Utilizator LucianTLucian Trepteanu LucianT Data 24 februarie 2016 16:57:42
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <bits/stdc++.h>
#define maxN 30005
#define UB(x) ((x)&(-x))
using namespace std;
int n, i, j, aib[maxN];
int val, poz, S;
int t, aux, k, sol;
void update(int pp, int x)
{
    int i;
    for(i = pp; i <= n; i += UB(i))
        aib[i] += x;
}
int sum(int x)
{
    int i;
    S=0;
    for(i = x; i > 0; i -= UB(i))
        S += aib[i];
    return S;
}
int CB(int st, int dr, int val)
{
    int mij;
    int sol = 1;
    int inter;
    int q = sum(st-1);
    while(st <= dr)
    {
        mij = (st+dr)>>1;
        inter = sum(mij)-q;
        if(inter == val)
            sol=mij, dr=mij-1;
        else if(inter > val) dr = mij-1;
             else st = mij+1;
    }
    return sol;
}
int chestie(int x)
{
    if(x < n) return x+1;
    if(x == n) return 1;
}
int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        update(i, 1);
    for(i=1; i<=n; i++)
    {
        sol = sum(n)-sum(poz);
        if(sol >= i)
        {
            t = CB(poz+1, n, i);
            printf("%d ", chestie(t));
            poz = t;
            update(poz, -1);
        }
        else
        {
            aux = i-sol;
            k = aux%(n+1-i);
            if(!k) k = n - i + 1;
            aux = CB(1, n, k);
            printf("%d ", chestie(aux));
            poz = aux;
            update(poz, -1);
        }
    }
    return 0;
}