Cod sursa(job #2952638)

Utilizator NanuGrancea Alexandru Nanu Data 9 decembrie 2022 17:32:40
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

#define DIM 30000
#define Ub(x) (x & -x)

int n;
int aib[DIM + 1];

static inline void Add(int poz, int val) {
  for(int i = poz; i <= n; i += Ub(i))
    aib[i] += val;
}

static inline int Suma(int poz) {
  int s = 0;
  for(int i = poz; i >= 1; i -= Ub(i))
    s += aib[i];

  return s;
}

static inline int CautBinarSt(int x) {
  int st = 1, dr = n, poz = 0;
  while(st <= dr) {
    int mid = (st + dr) >> 1;
    int S = Suma(mid);
    if(S == x) {
      poz = mid;
      dr = mid - 1;
    }else if(S < x)
      st = mid + 1;
    else dr = mid - 1;
  }
  return poz;
}

int main() {
  fin >> n;
  for(int i = 1; i <= n; i++)
    aib[i] = Ub(i);             //cati copii am in intervalul [i - 2^k + 1, i];
  
  int pas = 2, nr = n;
  for(int i = 1; i <= n; i++) {
    int poz = CautBinarSt(pas);   //pe cine elimin la pasul pas;
    fout << poz << " ";
    Add(poz, -1);

    pas += i;
    nr--;
    if(nr)
      pas = ((pas % nr) == 0 ? nr : pas % nr);
  }

  return 0;
}