Cod sursa(job #2555038)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 23 februarie 2020 17:12:15
Problema Order Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>

#define lsb(x) ((x ^ (x - 1)) & x)
#define Nmax 30005

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");

int N;
int bit[Nmax];
int pos = 0;

void update(int pos, int val)
{
    for(; pos <= N; pos += lsb(pos))
        bit[pos] += val;
}

int query(int pos)
{
    int ret = 0;
    for(; pos >= 1; pos -= lsb(pos))
        ret += bit[pos];
    return ret;
}

int main()
{
    fin >> N;
    for(int i = 1; i <= N; i++)
        update(i, 1);
    int cnt = 1, pos = 1, add = 0, idx = 0, sum = 0;
    for(int i = 1; i <= N;)
    {
        if(add == 0)
            add = max(1, i % (N - i + 1));
        idx = pos;
        for(int le = pos, ri = N; le <= ri;)
        {
            int mid = (le + ri) / 2;
            if(query(mid) - cnt < add)
            {
                idx = mid;
                le = mid + 1;
            }
            else
                ri = mid - 1;
        }
        sum = query(idx);
        if(idx == N)
        {
            add -= sum - cnt;
            pos = 0;
            cnt = 0;
        }
        else
        {
            pos = idx + 1;
            fout << pos << " ";
            update(pos, -1);
            cnt = query(pos);
            add = 0;
            i++;
        }
    }
    fout << "\n";
    return 0;
}