Cod sursa(job #3244328)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 24 septembrie 2024 15:48:28
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

const std :: string FILENAME = "order";

std :: ifstream f (FILENAME + ".in");

std :: ofstream g (FILENAME + ".out");

const int NMAX = 3e4 + 5;

int n;

int last;

int val;

int arb[NMAX];

int query(int x)
{
    int s = 0;

    while(x)
    {
        s += arb[x];

        x -= (x & (-x));
    }

    return s;
}

void update(int x, int val)
{
    while(x <= n)
    {
        arb[x] += val;

        x += (x & (-x));
    }
}

int cb(int x)
{
    int ret = 0;

    int s = 0;

    for(int i = (1 << 15); i > 0; i /= 2)
    {
        if(ret + i <= n && s + arb[ret + i] < x)
        {
            s += arb[ret + i];

            ret += i;
        }
    }

    return ret + 1;
}

int main()
{

    f >> n;

    for(int i = 1; i <= n; i ++)
    {
        update(i, 1);
    }

    last = 1;

    for(int i = 1; i <= n; i ++)
    {
        val = i;

        int fata = query(n) - query(last);

        if(fata < val)
        {
            val -= fata;

            int mod = query(n);

            val %= mod;
        }
        else
        {
            val += query(last);
        }

        if(val == 0)
        {
            val = query(n);
        }

        last = cb(val);

        update(last, -1);

        g << last << " ";//caut al i lea 1
    }

    return 0;
}