Cod sursa(job #496547)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 29 octombrie 2010 18:01:42
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<fstream>
using namespace std;
int n,v[30000];
int slr(int x)
{int s=0;
for(int i=x;i>=1;i-=((i)&(i-1))^(i) )
  s+=v[i];
return s;}
void update(int x,int val)
{for(int i=x;i<=n;i += ((i)&(i-1))^(i) )
  v[i]+=val;}
int caut(int kk)
{int m,st=1<<15;
for(m=1;st;st>>=1)
  if(m+st<=n&&slr(m+st-1)<kk)
   m+=st;
return m;}
int main()
{ifstream q("order.in");
ofstream w("order.out");
q>>n;
int p(1),po;
for(int i=1;i<=n;i++)
for(po=i,v[i]=1;!(po&1);po>>=1,v[i]<<=1);
  for(int i=0;i<n;++i)
	{po=caut((p=(p+i)%(n-i))+1);
    update(po,-1);
	w<<po<<" ";}
return 0;}