Cod sursa(job #749252)

Utilizator iris88Nagy Aliz iris88 Data 16 mai 2012 12:00:42
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <fstream>
#include <iostream>
#include <limits.h>
#include <time.h>
#include <stdio.h>
using namespace std;
typedef struct heapelem{
  int key,index;
}heapelem;

//heapelem heap[500001];
int secv[500001];
int baza[500001];
//void heapify(int k,int n)
//{
//  while (k<n){
//    int l = 2*k+1;
//    int r = 2*k+2;
//    int max = k;
//    if (l<n && heap[l].key<heap[k].key) max = l;
//    if (r<n && heap[r].key<heap[max].key) max= r;
//    if (max!=k)
//    {
//      int aux = heap[k].key;
//      heap[k].key=heap[max].key;
//      heap[max].key=aux;
//      aux = heap[k].index;
//      heap[k].index=heap[max].index;
//      heap[max].index=aux;
//      k=max;
//    }
//    else return;
//  }
//}
//void heapifyup(int k)
//{
//  while (k>0 && heap[k].key<heap[(k-1)/2].key)
//  {
//    int max = (k-1)/2;
//       int aux = heap[k].key;
//      heap[k].key=heap[max].key;
//      heap[max].key=aux;
//      aux = heap[k].index;
//      heap[k].index=heap[max].index;
//      heap[max].index=aux;
//    k = (k-1)/2;
//  }
//}
//heapelem* extractmin(int &n)
//{
//  int k=0;
//  int max = (n-1);
//  int aux = heap[k].key;
//  heap[k].key=heap[max].key;
//  heap[max].key=aux;
//  aux = heap[k].index;
//  heap[k].index=heap[max].index;
//  heap[max].index=aux;
//  n--;
//  heapify(0,n);
//  return &heap[n];
//}
int main()
{
  FILE *f= fopen("secventa.in","r");  
  int n,k;
  fscanf(f,"%d %d",&n,&k); 
  for (int i=0;i<n;i++)
    fscanf(f,"%d",&secv[i]);  
  fclose(f);
  int maxim;
  secv[n] = INT_MIN;
  int currmin = -1;
  baza[n] = INT_MIN;
  maxim =n;
  for (int i=0;i<n-k+1;i=currmin+1)
  {
    currmin =i;
    for (int j=i+1;j<k+i+1;j++)
      if (secv[j]<secv[currmin])
        currmin = j;
    baza[i] = secv[currmin];
    if (baza[i]>baza[maxim])
      maxim = i;
  }
 /* if (k==1)
  {
    maxim = secv[0];
    for (int i=1;i<n;i++)
      if (secv[i]>secv[maxim]) maxim = secv[i];
    baza[maxim] = secv[maxim];
  }
  else{
      for (int i=0;i<k;i++)
      {
        if (secv[i]<secv[i+1]){
          heap[heapsize].key=secv[i];
          heap[heapsize].index = i;
          heapifyup(heapsize);
          heapsize++;}
          baza[i]=heap[0].key;
        
      }
      maxim = k-1;    
      int i =k;
      while (i<n)
      {
        
          heap[heapsize].key = secv[i];
          heap[heapsize].index = i;
          heapifyup(heapsize);
          heapsize++;        
        while (heap[0].index<i-k+1)
        {
          extractmin(heapsize);
        }      
          baza[i] = secv[i];
        if (baza[i]>baza[maxim])
          maxim=i;
        i = heap[0].index+k;
      }
  }
*/
  ofstream g("secventa.out",ios::out);
  g<<maxim+1<<" "<<maxim+k<<" "<<baza[maxim]<<endl;
  g.close();  
  return 0;
}