Cod sursa(job #1556562)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 25 decembrie 2015 12:03:07
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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++;idx <= N;idx += idx & (-idx))
        bit[idx] += val;
}

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

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

    return sum;
}

int bs(int idx)
{
    int sol = -1;

    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 = 0;i < N;i++)
         update(i,1);

     int sol;

     for (int i = 0,j = 1;i < N;i++)
     {
         j = (j + i) % (N - i);
         sol = bs(j + 1);
         printf("%d ",sol + 1);

         update(sol,-1);
     }

     printf("\n");

  return 0;
}