Cod sursa(job #2836415)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 20 ianuarie 2022 12:43:07
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#include <algorithm>

#define MAXN 30000

using namespace std;

int aib[MAXN + 1];

inline int leastSemnificantBit( int x ) {
  return x & -x;
}

int getVal( int pos ) {
  int s = 0;
  while( pos ) {
    s += aib[pos];
    pos -= leastSemnificantBit(pos);
  }
  return s;
}

void update( int pos, int n ) {
  while( pos <= n ) {
    aib[pos]++;
    pos += leastSemnificantBit(pos);
  }
}

int v[MAXN];
int rez[MAXN];
bool f[MAXN + 1];

int changePos( int val, int n ) {
  int last, x;
  last = 0;
  x = getVal(val);
  while( x > last ) {
    val += x - last;
    last = x;
    x = getVal(val);
  }

  f[val] = true;
  update(val, n);
  return val;
}

int main() {
  FILE *fin, *fout;
  int n, i, x;
  fin = fopen( "schi.in", "r" );
  fscanf( fin, "%d", &n );
  for( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );

  for( i = n - 1; i >= 0; i-- ) {
    v[i] = changePos(v[i], n);
    rez[v[i] - 1] = i + 1;
  }

  fout = fopen( "schi.out", "w" );
  for( i = 0; i < n; i++ )
    fprintf( fout, "%d\n", rez[i] );
  return 0;
}