Cod sursa(job #3339409)

Utilizator unomMirel Costel unom Data 7 februarie 2026 20:54:30
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 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 st = poz;
        int dr = 2 * n;
        int ans = -1;
        int mij;

        while(st <= dr)
        {
            mij = (st + dr) / 2;

            if(query(mij) - query(poz - 1) >= moves)
            {
                ans = mij;
                dr = mij - 1;
            }
            else
            {
                st = mij + 1;
            }
        }

        if(ans == -1)
        {
            return 1;
        }

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

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

        poz = norm(ans);
    }

    return 0;
}