Pagini recente » Cod sursa (job #2778368) | Cod sursa (job #2049381) | Cod sursa (job #2692497) | Cod sursa (job #576962) | Cod sursa (job #969674)
Cod sursa(job #969674)
#include <stdio.h>
#define dim 500005
struct lista_elem {
int value;
int index;
struct lista_elem *next,*prev;
};
class LinkedList {
public:
/** Definiti membrii de care am nevoie*/
struct lista_elem *pfirst,*plast,*paux,*pp,*p;
int ok;
void add(int nr,int ind)
{
paux = new struct lista_elem;
paux -> value = nr;
paux -> index = ind;
if(pfirst == NULL) /**Daca n-am niciun numar in lista*/
{
paux->next = NULL;
paux->prev = NULL;
pfirst = paux;
plast = paux;
}
else
{
if(pfirst -> next == NULL) /**Daca am doar un nod in lista*/
{
if( pfirst->value < nr )
{
paux->next = NULL;
paux->prev = pfirst;
pfirst->next = paux;
plast = paux;
}
else
{
pfirst->prev = paux;
paux->next = pfirst;
pfirst = paux;
plast = pfirst->next;
}
}
else /**Daca am mai multe numere in lista*/
{
if( pfirst->value >= nr )
{
paux->next = pfirst;
pfirst->prev = paux;
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;
p->prev = paux;
paux->prev = pp;
pp->next = paux;
ok = 1;
break;
}
pp = p;
p = p->next;
}
if(!ok)
{
paux->next = NULL;
paux->prev = pp;
pp->next = paux;
plast = paux;
}
}
}
}
}
void addLast(int x, int ind)
{
struct lista_elem *paux;
paux = new struct lista_elem;
paux->value = x;
paux->index = ind;
paux->prev = plast;
paux->next = NULL;
if (plast != NULL) plast->next = paux;
plast = paux;
if (pfirst == NULL) pfirst = plast;
}
void del(int x)
{
p = plast;
while(p != NULL)
{
if(p->value >= x)
{
if(p->prev != NULL)
p->prev->next = NULL;
pp = p->prev;
plast = pp;
delete p;
p = pp;
}
else break;
}
}
void remove(int ind)
{
while(pfirst != NULL)
{
if(pfirst->index < ind)
{
if(pfirst->next != NULL)
pfirst->next->prev = NULL;
else plast = NULL;
p = pfirst;
pfirst = pfirst->next;
delete p;
}
else break;
}
}
LinkedList()
{
pfirst = NULL;
plast = 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;
//cautam secvente mai bune
for(i = K + 1; i <= N; i++)
{
fscanf(f,"%d",&x);
//stergem de la coada numerele mai mari decat x
Deque.del(x);
//stergem de la cap numerele care depasesc secventa
Deque.remove(i-K+1);
//adaugam la coada x
Deque.addLast(x,i);
if(Deque.pfirst->value > *min)
{
*min = Deque.pfirst->value;
*in = i - K + 1;
*sf = i;
}
}
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;
}