Cod sursa(job #828399)

Utilizator cahemanCasian Patrascanu caheman Data 3 decembrie 2012 18:51:25
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>

int aib[101010], n, m;
int tip, x, y; 

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

void add(int p, int x)
{
  int i;	
  for(i = p; i <= n; i += lsb(i))  
	aib[i] += x;
}

int querry(int p)
{    
  int s = 0, i;
  for(i = p; i >= 1; i -= lsb(i)) 
	s += aib[i];
  return s; 
}

int bs(int val)
{
  int st = 1, dr = n, mij, rez = 0;
  while(st <= dr)
  {       
	mij = ((dr - st) >> 1) + st;   
	x = querry(mij);  
	if(x == val)   
	  rez = mij; 
	if(x >= val)
	  dr = mij - 1;
	else
	  st = mij + 1; 
  }  
  return rez;
}

int main()
{
  freopen("order.in", "r", stdin);
  freopen("order.out", "w", stdout); 
  int i, q, nr, a = 1;
  scanf("%d", &n);
  for(i = 1; i <= n; i ++)
	add(i, 1);  
  nr = n; 
  for(i = 1; i <= n; i ++) 
  {      
    a += i;    
    a %= nr;
    if(a  ==  0)
	  a = nr; 
    q = bs(a); 
    printf("%d ", q); 
    add(q, -1);  
    nr --;  
	a --;  
	if(a == 0) 
	  a = nr;   
  }
  return 0;
}