Cod sursa(job #2604055)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 21 aprilie 2020 15:52:36
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>

#define NMAX 30000

using namespace std;

int aib [ NMAX + 1 ] ;

int lsb (int x ) {
  return x & (-x) ;
}

void update (int poz, int val) {
  int i ;
  for ( i = poz ; i < NMAX ; i += lsb(i) )
    aib[i] += val ;
}

int query (int poz ) {
  int ans, i ;
  ans = 0 ;
  for (i = poz ; i > 0 ; i-=lsb(i) )
    ans += aib[i] ;
  return ans ;
}

int cautbin (int val, int n ) {
  int st, dr, mid ;
  st = 0 ;
  dr = n+1 ;
  while (st < dr ) {
    mid = (st + dr ) / 2 ;
    if (query(mid) >= val )
      dr = mid ;
    else
      st = mid + 1;
  }
  return st ;
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("order.in", "r" ) ;
  fout = fopen ("order.out", "w" ) ;
  int n, i, x, poz, size, caut ;
  fscanf (fin, "%d", &n ) ;
  for (i = 1 ; i <= n ; i++ )
    update(i, 1) ;
  size = n ;
  poz = 1 ;
  i = 1 ;
  for (caut = 1 ; caut < n ; caut++ ) {
    i = caut ;
    i %= size ;
    if (query(n) - query(poz) < i )
      i = size - i ;
    else
      i += query(poz) ;
    if (i == 0 )
      i = size ;
    poz = cautbin(i, n) ;
    fprintf(fout, "%d ", poz ) ;
    update(poz, -1) ;
    size--;
    i++;
  }
  poz = cautbin(1, n) ;
  fprintf(fout, "%d", poz ) ;
  return 0;
}