Cod sursa(job #3229149)

Utilizator andreifilimonPopescu Filimon Andrei Cosmin andreifilimon Data 14 mai 2024 08:57:40
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#include <vector>

using namespace std;

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

#define MAXN 100000

int n;
vector<int> bit(MAXN + 1, 0);

void update(int i, int val) {
  while (i <= n) {
    bit[i] += val;
    i += (i & -i);
  }
}

int prefixSum(int i) {
  int sum;
  sum = 0;
  while (i > 0) {
    sum += bit[i];
    i -= (i & -i);
  }
  return sum;
}

int main() {
  cin >> n;

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

  int poz, dr, st, mij;
  poz = 2;
  for (i = 1; i <= n; i++) {
    poz = (poz + n - 1) % (n - i + 1) + 1;
    st = 1;
    dr = n;
    while (st < dr) {
      mij = (st + dr) / 2;
      if (prefixSum(mij) >= poz)
        dr = mij;
      else
        st = mij + 1;
    }
    cout << dr << " ";
    update(dr, -1);
  }
}