Cod sursa(job #2642670)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 16 august 2020 18:13:00
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <cstdio>
using namespace std;
const int NMAX = 30000;
int aint[NMAX + 5];
void build(int st , int dr , int nod)
{
    if(st == dr)
        aint[nod] = 1;
    else
    {
        int med = (st + dr) / 2;
        build(st , med , nod << 1);
        build(med + 1 , dr , (nod << 1)|1);
        aint[nod] = aint[nod << 1] + aint[(nod << 1)|1];
    }
}
int ql , qr , sum , val , sol;
int viz[NMAX + 5];
void query(int st , int dr , int nod)
{
    //printf("st = %d dr = %d nod = %d ql = %d qr = %d sum = %d val = %d\n" , st , dr , nod , ql , qr , sum , val);
    /*if(st == dr)
    {
        aint[nod] = 0;
        sol = st;
        sum = val;
        return;
    }*/
    int med = (st + dr) / 2;
    if(ql <= st && dr <= qr && sum < val)
    {
        if(sum + aint[nod] < val)
        {
            sum += aint[nod];
            return;
        }
        else
        {
            if(st == dr)
            {
                aint[nod] = 0;
                sol = st;
                sum = val;
                return;
            }
            if(sum + aint[nod << 1] >= val)
                query(st , med , nod << 1);
            else
            {
                sum += aint[nod << 1];
                query(med + 1, dr , (nod << 1)|1);
            }
        }
    }
    else
    {
        if(ql <= med && sum < val)
            query(st , med , nod << 1);
        if(qr > med && sum < val)
            query(med + 1 , dr , (nod << 1)|1);
    }
    aint[nod] = aint[nod << 1] + aint[(nod << 1)|1];
}
int main()
{
    freopen("order.in" , "r" , stdin);
    freopen("order.out" , "w" , stdout);
    int n , i , last , current;
    scanf("%d" , &n);
    build(1 , n , 1);
    last = 1;
    /*sum = 0;
    val = 1;
    ql = 2;
    qr = n;
    query(1 , n , 1);
    printf("%d\n" , sol);*/
    for(i = 1 ; i <= n ; i ++)
    {
        sol = -1;
        val = i;
        sum = 0;
        ql = last + 1;
        qr = n;
        query(1 , n , 1);
        //printf("%d %d\n" , val , sum);
        if(sol == -1)
        {
            val = (val - sum) % aint[1];
            sum = 0;
            ql = 1;
            qr = n;
            query(1 , n , 1);
        }
        if(sol != -1)
        printf("%d " , sol);
        viz[sol] = 1;
        last = sol;
        if(last == n)
            last = 1;
    }
    for(i = 1 ; i <= n && viz[i] ; i ++);
    printf("%d\n" , i);
    return 0;
}