Cod sursa(job #1363828)

Utilizator Darius15Darius Pop Darius15 Data 27 februarie 2015 11:43:35
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#define zeros(x) ((x^(x-1))&x)
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int n,v[60001],pi,i,pas,l,val,y;
void adauga(int val,int l)
{
    int i;
    for (i=l;i<=2*n;i+=zeros(i))
        v[i]+=val;
}
int suma(int l)
{
    int i,sum=0;
    for (i=l;i>=1;i-=zeros(i))
      sum+=v[i];
    return sum;
}
int cauta(int val)
{
   int i,p=pi;
   for (i=0;p;p>>=1)
      if (i+p<=2*n)
        if (v[i+p]<val)
       i+=p,val-=v[i];
return i+1;
}
int main()
{
    f>>n;
    for (i=1;i<=2*n;i++)
    adauga(1,i);
    for (pi=1;pi<2*n;pi<<=1);
    for (pas=1,l=1;pas<=n;pas++)
    {
        if ((suma(l)+pas)%suma(n)==0)
            val=suma(n);
        else val=(suma(l)+pas)%suma(n);
       y=cauta(val);
       if (y>n) y=y%n;
       adauga(-1,y),adauga(-1,y+n);
       l=y;
       g<<l<<' ';
    }
    return 0;
}