Cod sursa(job #2163273)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 12 martie 2018 17:36:03
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("order.in");
ofstream out ("order.out");
int const nmax = 30000;
int const lgmax = 16;
int aib[5 + 4 * nmax];

#define MAX(a , b) ((a < b) ? b : a)
#define MIN(a , b) ((a < b) ? a : b)
int n;
void update(int x ,int val){
  while(x <= n){
    aib[x] += val;
    x = x + (x ^ (x & (x - 1)));
  }
}
int main()
{
  in >> n;
  for(int i = 1 ; i <= n ;i++)
    update(i , 1);

  int node = 2;
  for(int i = 1 ; i <= n ;i++){
    int pos = (node + i - 2) % (n - i + 1) + 1;
    int result = 0;
    int posnew = 0;
    for(int h = lgmax ; 0 <= h ;h--){
      if(posnew + (1 << h) < n){
        if(result + aib[posnew + (1 << h)] < pos){
          result += aib[posnew + (1 << h)];
          posnew += (1 << h);
        }
      }
    }
    posnew++;
    update(posnew , -1);
    out << posnew << " ";
    node = pos;
  }
  return 0;
}