Cod sursa(job #2555046)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 23 februarie 2020 17:17:57
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 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;
bool vis[Nmax];

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 = 1 + (i - 1) % (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 << " ";
            vis[pos] = true;
            update(pos, -1);
            cnt = query(pos);
            add = 0;
            i++;
        }
    }
    for(int i = 1; i <= N; i++)
        if(!vis[i])
            fout << i << "\n";
    return 0;
}