Pagini recente » Cod sursa (job #1497731) | Cod sursa (job #1539379) | REZULTATE | Cod sursa (job #1125889) | Cod sursa (job #969564)
Cod sursa(job #969564)
#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;
}