Cod sursa(job #1425509)

Utilizator hrazvanHarsan Razvan hrazvan Data 27 aprilie 2015 16:19:30
Problema Order Scor 100
Compilator c Status done
Runda pregatire-lot-aib Marime 0.84 kb
#include <stdio.h>
#define MAXN 30000
int aib[MAXN + 1];

inline int ultb(int x){
  return x & (-x);
}

inline int caut(int p, int n){
  int i = 0, pas = 1 << 14, sum = 0;
  while(pas > 0){
    if(i + pas <= n && sum + aib[i + pas] < p){
      sum += aib[i + pas];
      i += pas;
    }
    pas >>= 1;
  }
  return i + 1;
}

void add(int p, int val, int n){
  if(p <= n){
    aib[p] += val;
    add(p + ultb(p), val, n);
  }
}

int main(){
  FILE *in = fopen("order.in", "r");
  int n;
  fscanf(in, "%d", &n);
  fclose(in);
  FILE *out = fopen("order.out", "w");
  int i, p = 0, x;
  for(i = 1; i <= n; i++){
    if(i & 1)
      aib[i] = 1;
    else
      aib[i] = 2 * aib[i >> 1];
  }
  for(i = 1; i <= n; i++){
    p += i;
    p %= n - i + 1;
    x = caut(p + 1, n);
    p--;
    add(x, -1, n);
    fprintf(out, "%d ", x);
  }
  fclose(out);
  return 0;
}