Cod sursa(job #1394385)

Utilizator hrazvanHarsan Razvan hrazvan Data 20 martie 2015 11:50:36
Problema Subsir 2 Scor 55
Compilator c Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#define MAXN 5000
int v[MAXN], point[MAXN], rez[MAXN];

void qs(int st, int dr){
  int i = st, j = dr, piv = v[point[(st + dr) / 2]], pivp = point[(st + dr) / 2], aux;
  while(i <= j){
    while(v[point[i]] < piv || (v[point[i]] == piv && point[i] < pivp))
      i++;
    while(v[point[j]] > piv || (v[point[j]] == piv && point[j] > pivp))
      j--;
    if(i <= j){
      aux = point[i];
      point[i] = point[j];
      point[j] = aux;
      i++;
      j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

int main(){
  FILE *in = fopen("subsir2.in", "r");
  int n, i;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%d", &v[i]);
    point[i] = i;
  }
  fclose(in);
  qs(0, n - 1);
  int last = -1, dr = 0;
  for(i = 0; i < n; i++){
    if(point[i] > last){
      last = point[i];
      rez[dr] = point[i] + 1;
      dr++;
    }
  }
  FILE *out = fopen("subsir2.out", "w");
  fprintf(out, "%d\n", dr);
  for(i = 0; i < dr; i++)
    fprintf(out, "%d ", rez[i]);
  fclose(in);
  return 0;
}