Cod sursa(job #227979)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 6 decembrie 2008 01:00:46
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>

using namespace std;

ifstream fin ("order.in");
ofstream fout ("order.out");

int n,heap[300000],caut,poz[300000];

void baga(int nod, int st,int dr)
{
     if (st==dr)
     {
          heap[nod]=1;
          poz[st]=nod;
          return ;
     }
     int mij=(st+dr)>>1;
     int nst=nod<<1;
     int ndr=(nod<<1)+1;
     baga(nst,st,mij);
     baga(ndr,mij+1,dr);
     heap[nod]=heap[ndr]+heap[nst];
}

void calc(int nod,int st,int dr)
{
     if (st==dr)
     {
          heap[nod]=0;
          fout<<st<<" ";
          return ;
     }
     int mij=(st+dr)>>1;
     int nst=nod<<1;
     int ndr=(nod<<1)+1;

     if (caut<=heap[nst])
          calc(nst,st,mij);
     else
     {
          caut-=heap[nst];
          calc(ndr,mij+1,dr);
     }
     heap[nod]=heap[nst]+heap[ndr];
}

int main ()
{
     fin>>n;
     baga(1,1,n);
     int poz=2;
     caut=2;
     calc(1,1,n);
     for (int i=2;i<=n;i++)
     {
          poz+=(i-1);
          poz%=(n-i+1);
          caut=poz;
          if (poz==0)
          {
               fout<<n<<"\n";
               return 0;
          }
          calc(1,1,n);
     }
     return 0;
}