Cod sursa(job #969564)

Utilizator bugyBogdan Vlad bugy Data 4 iulie 2013 18:10:05
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <stdio.h>
#define dim 500005

struct lista_elem {
    int value;
	int index;
	struct lista_elem *next;
};

class LinkedList {
   
	public: 
	/** Definiti membrii de care am nevoie*/
		
	struct lista_elem *pfirst,*paux,*pp,*p;
	int size,ok;
    
	void add(int nr,int ind) {
	
	size++;	
	paux = new struct lista_elem;
    paux -> value = nr;
    paux -> index = ind;
	
	if(pfirst == NULL) /**Daca n-am niciun numar in lista*/
	{
		paux->next = NULL;
		pfirst = paux; 
		
	}
	else
	{
		if(pfirst-> next == NULL) /**Daca am doar un numar in lista*/
		{
			if( pfirst->value < nr )
			{
				paux->next = NULL;
				pfirst->next = paux;
			}
			else 
			{
				paux->next = pfirst;
				pfirst = paux;			
			}
				
		}
		else	 /**Daca am mai multe numere in lista*/
		{
			if( pfirst->value >= nr )
			{
				paux->next = pfirst;
				pfirst = paux;	
			}
			else 
			{
				pp = pfirst;
				p =  pfirst->next;
				ok = 0;
				while(p != NULL)
				{
					if( p->value < nr ) 
					{
						pp = p;
						if(p->next != NULL)
						{
							p = p->next;
							continue;
						}
						else break;
					}
					else 
					{
						paux->next = p;
						pp->next = paux; 						
						ok = 1;
						break;
					}
					
				pp = p;
				p = p->next;
				}
			
				if(!ok)
				{
					paux->next = NULL;
					pp->next = paux;
				}
			}
		}
	}	
	}
	
	void remove(int ind)
	{
		p =  pfirst;
		pp = p->next;
			
		while(pp != NULL)
		{
			
			if(pp->index < ind)
			{
				p->next = pp->next;
				delete pp;
				
				size --;
				pp = p->next;	
			}
			else
			{
				p = p->next;
				pp = p->next;	
			}
						
		}		
		
		if(p!=NULL)
		{
			p = pfirst->next;
			delete pfirst;
			size --;
			pfirst = p;
		}
	}
	
    LinkedList()
	{
		pfirst = NULL;
	}
   ~LinkedList(){}
   
  
};





void citire(int *in,int *sf, int *min)
{
	int i,N,K,x;
	
	LinkedList Deque;
	
	FILE *f=fopen("secventa.in","r");
	
	fscanf(f,"%d %d",&N,&K);
	
	//citim primele K numere
	for(i = 1; i <=  K; i++)
	{
		fscanf(f,"%d",&x);
		Deque.add(x,i);
		if(x < *min)
		{
			*min = x;
		}
	}
		
	//initializam prima secventa
	*in = 1;
	*sf = K;
	Deque.size = K;
	
	//cautam secvente mai bune
	for(i = K + 1; i <= N; i++)
	{
		fscanf(f,"%d",&x);
		Deque.add(x,i);
		Deque.remove(Deque.pfirst->index);	
	
	//daca Secventa are K, facem poza
	if(Deque.size == K)
	{
		if(Deque.pfirst->value > *min)
		{
			*min = Deque.pfirst->value;
			*sf = i;
			*in = i - K + 1;
		}
	}
	//altfel completam pana la K si facem poza
	else
	{
		while(Deque.size < K && i <= N)
		{
			fscanf(f,"%d",&x);
			Deque.add(x,i);
			i++;
		}
		
		if(Deque.size == K)
		{
			if(Deque.pfirst->value > *min)
			{
				*min = Deque.pfirst->value;
				*sf = i;
				*in = i - K + 1;
			}
		}
	}
	}
	
fclose(f);
}

void afisare(int in,int sf, int min)
{
	FILE *g = fopen("secventa.out","w");
	
	fprintf(g,"%d %d %d\n", in, sf, min);
	
fclose(g);
}

int main()
{
	int in, sf, min;
	
	citire(&in, &sf, &min);
	afisare(in,sf,min);
	

return 0;
}