Cod sursa(job #2769770)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 17 august 2021 17:11:05
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>

using namespace std;

const int NMAX = 30000;

int n;
int aib[1 + NMAX];

int ord[1 + NMAX];

inline int lsb(const int val)
{
  return val & -val;
}

int query(int i)
{
  int sol = 0;

  for (; i > 0; i -= lsb(i))
    sol += aib[i];

  return sol;
}

void update(int i, int val)
{
  for (; i <= n; i += lsb(i))
    aib[i] += val;
}

int caut(int val)
{
  int sol = 0;
  int pow2 = 1;
  while (pow2 * 2 <= n)
    pow2 *= 2;

  for (; pow2 > 0; pow2 >>= 1)
  {
    int pos = sol + pow2;
    if (pos <= n && aib[pos] < val)
    {
      sol = pos;
      val -= aib[pos];
    }
  }
  sol++;

  return sol;
}

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

  in >> n;

  for (int i = 1; i <= n; i++)
  {
    aib[i] += 1;
    if (i + lsb(i) <= n)
      aib[i + lsb(i)] += aib[i];
  }

  int pos = 1;

  for (int i = 1; i <= n; i++)
  {
    int ramase = n - i + 1;

    int nrPasi = query(pos) + i % ramase;
    if (nrPasi > ramase)
      nrPasi -= ramase;
    if (nrPasi == 0)
      nrPasi = ramase;

    pos = caut(nrPasi);

    update(pos, -1);
    ord[i] = pos;
  }

  for (int i = 1; i <= n; i++)
    out << ord[i] << ' ';
  out << '\n';

  return 0;
}