Cod sursa(job #2986315)

Utilizator Luca529Taschina Luca Luca529 Data 28 februarie 2023 11:33:55
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int x[400001];

void Build(int nod, int st, int dr)
{if(st==dr)
 x[nod]=1;
 else
 {int mij=(st+dr)/2;

  Build(nod*2, st, mij);
  Build(nod*2+1, mij+1, dr);

  x[nod]=x[nod*2]+x[nod*2+1];
 }
}

int G(int nod, int st, int dr, int p)
{if(st==dr)
 return st;
 else
 {int mij=(st+dr)/2;

  if(x[nod*2]>=p)return G(nod*2, st, mij, p);
  else return G(nod*2+1, mij+1, dr, p-x[nod*2]);
 }
}

void Update(int nod, int st, int dr, int p)
{if(dr==st)
 x[nod]=0;
 else
 {int mij=(st+dr)/2;

  if(mij>=p)Update(nod*2, st, mij, p);
  else Update(nod*2+1, mij+1, dr, p);

  x[nod]=x[nod*2]+x[nod*2+1];
 }
}

int main()
{   int n, p=2, a;
    fin>>n;
    Build(1, 1, n);

    for(int i=1;i<=n;i++)
    {a=G(1, 1, n, p);
     Update(1, 1, n, a);

     p+=i;
     if(i!=n)p%=(n-i);
     if(p==0)p=n-i;

     fout<<a<<" ";
    }
    return 0;
}