Cod sursa(job #3339411)

Utilizator unomMirel Costel unom Data 7 februarie 2026 20:57:34
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>

using namespace std;

ifstream in("order.in");
ofstream out("order.out");
int n;
int aib[60005];

void build()
{
    for(int i = 1; i<=2*n; i++)
    {
        aib[i]++;

        int nxt = i + (i&-i);
        if(nxt <= 2 * n)
        {
            aib[nxt] += aib[i];
        }
    }
}

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

int query(int poz)
{
    int ans = 0;

    for(int i = poz; i>=1; i-=(i&-i))
    {
        ans += aib[i];
    }

    return ans;
}

int norm(int x)
{
    if(x <= n)
    {
        return x;
    }

    return x - n;
}

int ech(int x)
{
    if(x <= n)
    {
        return x + n;
    }

    return x - n;
}

int main()
{
    in>>n;

    build();

    int poz = 2;
    for(int i = 1; i<=n; i++)
    {
        int ramas = n - i + 1;
        int moves = (i % ramas);

        if(moves == 0)
        {
            moves = ramas;
        }

        int dif = query(poz - 1);
        int ans = 0;
        int sum = 0;

        for(int j = 20; j>=0; j--)
        {
            if(ans + (1 << j) <= 2 * n && sum + aib[ans + (1 << j)] - dif < moves)
            {
                sum += aib[ans + (1 << j)];
                ans += (1 << j);
            }
        }

        ans++; //ca sa fie >= moves

        out<<norm(ans)<<" ";

        update(ans, -1);
        update(ech(ans), -1);

        poz = norm(ans);
    }

    return 0;
}