Cod sursa(job #2436574)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 6 iulie 2019 13:14:14
Problema Sortare prin comparare Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>
#define maxn 500000
#define DIM (1<<17)

FILE *fin, *fout;
char BUFF[DIM+5];
int kbu;

void _reset ()
{
  if ( kbu == DIM )
  {
    fread ( BUFF, 1, DIM, fin );
    kbu = 0;
  }
}

void _read ( int &nr )
{
  nr = 0;
  while ( BUFF[kbu] < '0' || BUFF[kbu] > '9' )
  {
    kbu++;
    _reset ();
  }
  while ( BUFF[kbu] >= '0' && BUFF[kbu] <= '9' )
  {
    nr = nr * 10 + BUFF[kbu++] - '0';
    _reset ();
  }
}

namespace ctl
{
  struct nod
  {
    int lson, rson, val, amt;
  };
  void add_val ( std::vector<int> &v, std::vector<ctl::nod> &g, int p, int x )
  {
    if (g[p].val == v[x]) { g[p].amt++; return; }
    if (g[p].val < v[x])
    {
      if (g[p].rson == 0) g[p].rson = x, g[x] = {0, 0, v[x], 1};
      else ctl::add_val (v, g, g[p].rson, x);
    }
    else
    {
      if (g[p].lson == 0) g[p].lson = x, g[x] = {0, 0, v[x], 1};
      else ctl::add_val (v, g, g[p].lson, x);
    }
  }
  void dfs ( std::vector<ctl::nod> &g, std::vector <int> &ans, int x )
  {
    if (g[x].lson != 0) ctl::dfs (g, ans, g[x].lson);
    for (int i = 0; i < g[x].amt; i++ ) ans.push_back (g[x].val);
    if (g[x].rson != 0) ctl::dfs (g, ans, g[x].rson);
  }
  std::vector <int> sort ( std::vector<int> v )
  {
    int n = v.size();
    v.push_back(0);
    int i, j, z;
    for ( i = n; i >= 1; i-- ) v[i] = v[i-1];
    std::vector <ctl::nod> g(n+1);
    g[1] = {0, 0, v[1], 1};
    for ( i = 2; i <= n; i++ ) ctl::add_val (v, g, 1, i);
    std::vector <int> ans;
    ctl::dfs (g, ans, 1);
    return ans;
  }
}

std::vector<int> v;

int main ()
{
  fin = fopen ( "algsort.in", "r" );
  fout = fopen ( "algsort.out", "w" );
  int n; _read(n);
  int i, j, z;
  for ( i = 0; i < n; i++ ) _read(z), v.push_back(z);
  v = ctl::sort (v);
  for (int z: v) fprintf ( fout, "%d ", z );
  return 0;
}