Cod sursa(job #2904557)

Utilizator larisa-ioana.virtejanuLarisa Ioana Virtejanu larisa-ioana.virtejanu Data 18 mai 2022 00:00:45
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 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;
}