Cod sursa(job #1303699)

Utilizator DjokValeriu Motroi Djok Data 28 decembrie 2014 12:35:30
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<fstream>
#include<algorithm>
using namespace std;

int arb[30005],i,n,poz=1,rs;

void update(int poz,int aux) {
     while(poz<=n) arb[poz]+=aux,poz+=-poz&poz;
}

int query(int poz) {
     int rs=0;
     while(poz>=1) rs+=arb[poz],poz-=-poz&poz;
     return rs;
}

int Search(int x) {
    int st=1,dr=n,pivot;

    while(st<=dr)
    {
      pivot=(st+dr)/2;
      if(query(pivot)<x) st=pivot+1;
      else dr=pivot-1;
    }
    return st;
}

int main()
{
  ifstream cin("order.in");
  ofstream cout("order.out");

  cin>>n;
  for(i=1;i<=n;++i) update(i,1);

  for(i=1;i<=n;++i)
  {
    poz+=i; poz%=n-i+1;
    if(!poz) poz=n-i+1;
    rs=Search(poz);
    update(rs,-1);
    poz=query(rs);
    cout<<rs<<' ';
  }
    
 return 0;
}