Cod sursa(job #2777955)

Utilizator cyg_dragos10Ivan Dragos cyg_dragos10 Data 26 septembrie 2021 17:12:33
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>

using namespace std;

ifstream cin("order.in");
ofstream cout("order.out");

int n;

const int NMAX = 30005;

int aib[NMAX];

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

int query(int i)
{
    int sum = 0;
    for(;i > 0;i -= i & -i)
        sum += aib[i];
    return sum;
}

int bs(int val)
{
    int st = 1,dr = n;
    while(st <= dr)
    {
        int mij = st + (dr - st) / 2;
        if(query(mij) <= val)
            st = mij + 1;
        else
            dr = mij - 1;
    }
    return dr;
}

int main()
{
    cin>>n;
    for(int i = 1;i <= n;i++)
        update(i, 1);
    int poz = 2;
    for(int i = 1; i <= n; i ++)
    {
        poz = (poz + i - 1) % (n - i + 1);
        if(poz == 0)
            poz = n -  i + 1;
        int sol = bs(poz);
        while(query(sol) == poz)
        sol--;
        sol++;
        update(sol, -1);
        cout<<sol<<" ";
    }
    return 0;
}