Cod sursa(job #1419738)

Utilizator Alex1199Alex Bercea Alex1199 Data 16 aprilie 2015 12:41:06
Problema Statistici de ordine Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.39 kb
#include <stdio.h>
#include <algorithm>
long int n,k, v[3000001];
FILE *f=fopen("sdo.in","r");
FILE *g=fopen("sdo.out","w");
long int partiton(long int l, long int r, long int k){
  long int i=l, j=r, x=v[(l+r)/2];
  while (i<j){
    while (v[i]<x)i++;
    while (v[j]>x)j--;
     if(i<=j){
      std::swap(v[i],v[j]);
        i++; j--;
     }
  }
  if(l<=k&&k<j) return partiton(l,j,k);
  if (i<=k&& k<=r) return partiton(i,r,k);
 return v[k];
}
int main(){
 long int i;
 fscanf(f,"%ld%ld",&n,&k);
 for(i=1;i<=n;i++){
    fscanf(f,"%ld",&v[i]);
 }
fprintf(g,"%ld\n",partiton(1,n,k));
    return 0;
}









//#include <stdio.h>
//int v[1000000];
//
//int main() {
//  FILE *fin, *fout;
//  int n, k, i, begin, end, b, e, pivot, aux;
//
//  fin = fopen( "selectie.in", "r" );
//  fscanf( fin, "%d%d", &n, &k );
//  for ( i = 0; i < n; i++ )
//    fscanf( fin, "%d", &v[i] );
//  fclose( fin );
//
//  k--;
//  begin = 0;
//  end = n - 1;
//  while ( begin < end ) {
//    b = begin;
//    e = end;
//    pivot = v[(begin + end) / 2]; // alegem un pivot la jumatea vectorului
//    while ( b <= e ) {
//      while ( v[b] < pivot ) b++;
//      while ( v[e] > pivot ) e--;
//      if ( b <= e ) {
//        aux = v[b]; v[b] = v[e]; v[e] = aux;
//        b++; e--;
//      }
//    }
//    // acum [begin..e] sint mai mici sau egale cu pivotul
//    // si [b..end] sint mai mari sau egale cu pivotul
//    if ( k <= e )
//      end = e;
//    else if ( k >= b )
//      begin = b;
//    else
//      begin = end = k;
//  }
//
//  fout = fopen( "selectie.out", "w" );
//  fprintf( fout, "%d\n", v[k] );
//  fclose( fout );
//
//  return 0;
//}

//#include <stdio.h>
//#include <algorithm>
//int n, m, a[1000001];
//FILE *f,*g;
//int part(int s, int d){
//
// int i=s, j=d, x=a[(s+d)/2];
// while(i<j){
//    while(a[i]<x)i++;
//    while(a[j]>x)j--;
//    if(i<=j){
//   std::swap(a[i],a[j]);
//        i++;j--;
//    }
// }
//// fprintf(g,"i=%d    j=%d     k=%d\n",i-1,j,m);
// if(i-1==m) fprintf(g,"%d",a[m]);
// if(i-1<m) part(i,d);
// if(i-1>m) part(s,i-1);
//}
//int main(){
//  f=fopen("selectie.in","r");
//  g=fopen("selectie.out","w");
// fscanf(f,"%d%d",&n,&m);
// for(int i=1;i<=n;i++){
//    fscanf(f,"%d",&a[i]);
// }
// part(1,n);
// //for(int i=1;i<=n;i++){
//  //  fprintf(g,"%d ",a[i]);
// //}
//    return 0;
//}