Cod sursa(job #1556573)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 25 decembrie 2015 12:39:20
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int MN = 30005;

int N;
int bit[MN];

void update(int idx,int val)
{
    for (;idx <= N;idx += idx & (-idx))
        bit[idx] += val;
}

int query(int idx)
{
    int sum = 0;

    for (;idx;idx -= idx & (-idx))
        sum += bit[idx];

    return sum;
}

int bs(int idx)
{
    int sol =  0;

    for (int it = 1 << 15;it;it >>= 1)
        if (sol + it < N && query(sol + it) < idx)
           sol += it;

    return sol + 1;
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);

     scanf("%d",&N);

     for (int i = 1;i <= N;i++)
         update(i,1);

     for (int i = 1,j = 2;i <= N;i++)
     {
         j = (j + i - 1) % (N - i + 1);

         if (!j)
            j = N - i + 1;

         int sol = bs(j);

         printf("%d ",sol);
         update(sol,-1);
     }

     printf("\n");

  return 0;
}