Cod sursa(job #2684140)

Utilizator Razvan667Cutuliga Razvan Razvan667 Data 12 decembrie 2020 23:19:32
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
using namespace std;

const int NMAX = 30000;

int part[1 + NMAX];
int last[1 + NMAX];

int aint[3 * NMAX];

void build(int idx, int st, int dr)
{
  if (st == dr)
  {
      aint[idx] = 1;
    return;
  }

  int mij = (st + dr) / 2;
  int nou_st = idx * 2;
  int nou_dr = idx * 2 + 1;

  build(nou_st, st, mij);
  build(nou_dr, mij + 1, dr);

  aint[idx] = aint[nou_st] + aint[nou_dr];

}

int query(int idx, int st, int dr, int val)
{
  if (st == dr)
  {
    aint[idx]--;
    return st;
  }

  int mij = (st + dr) / 2;
  int nou_st = idx * 2;
  int nou_dr = idx * 2 + 1;

  if (val <= aint[nou_st])
  {
    aint[idx]--;
    return query(nou_st, st, mij, val);
  }
  else
  {
    aint[idx]--;
    return query(nou_dr, mij + 1, dr, val - aint[nou_st]);
  }
}

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

  int n;

  in >> n;
  for (int i = 1; i <= n; i++)
  {
    in >> part[i];
  }

  build(1, 1, n);

  for (int i = n; i >= 1; i--)
  {
    int poz = query(1, 1, n, part[i]);
    last[poz] = i;
  }

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

  return 0;
}