Cod sursa(job #2097037)

Utilizator GoogalAbabei Daniel Googal Data 30 decembrie 2017 13:49:57
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#define zeros(x)(x&(-x))

using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");

const int NMAX = 30000;

int n;
int v[1 + NMAX];
int sol[1 + NMAX];
int aib[1 + NMAX];

int sum(int x) {
  int s = 0;
  for(int i = x; i >= 1; i -= zeros(i))
    s += aib[i];
  return s;
}

void add(int x) {
  for(int i = x; i <= n; i += zeros(i))
    aib[i]--;
}

int src(int x) {
  int st = 1;
  int dr = n;
  int mid;

  while(st <= dr) {
    mid = (st + dr) / 2;
    if(sum(mid) < x)
      st = mid + 1;
    else
      dr = mid - 1;
  }

  add(dr + 1);
  return dr + 1;
}

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

  for(int i = 1; i <= n; i++)
    aib[i] = zeros(i);

  for(int i = n; i >= 1; i--)
    sol[src(v[i])] = i;

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

  in.close();
  out.close();
  return 0;
}