Pagini recente » Cod sursa (job #1164556) | Borderou de evaluare (job #269413) | Cod sursa (job #84686) | Cod sursa (job #1584841) | Cod sursa (job #978166)
Cod sursa(job #978166)
#include <iostream>
#include <fstream>
using namespace std;
#define MAX 500002
int k, n, v[MAX], x[MAX], xlen, xbase = MAX, xmin, xmax;
struct node {
int index;
node* next;
};
node *xstart;
void print(){
cout << endl;
cout << n << " " << k << endl;
for(int i = 0; i < n; i ++){
cout << v[i] << " ";
}
cout << endl;
cout << xmin+1 << " " << xmax+1 << " " << v[xbase] << endl;
cout << endl;
}
void printx(){
node* xindex;
xindex = xstart;
while (xindex != NULL){
cout << xindex->index << " ";
xindex = xindex->next;
}
cout << endl;
xindex = xstart;
while (xindex != NULL){
cout << v[xindex->index] << " ";
xindex = xindex->next;
}
cout << endl;
}
void insertion(int p){
node *xindex, *xnew;
xnew = new node();
xnew->index = p;
xlen ++;
if(xstart == NULL){
xnew->next = NULL;
xstart = xnew;
} else if(xstart->index > v[p]){
xnew->next = xstart;
xstart = xnew;
} else {
xindex = xstart;
while (xindex->next != NULL){
if(v[xindex->next->index] > v[p]){
break;
}
xindex = xindex->next;
}
xnew->next = xindex->next;
xindex->next = xnew;
}
//printx();
}
void removemin(){
int min;
node *xindex;
if (xstart == NULL) return;
min = xstart->index;
while (xstart != NULL && xstart->index <= min){
xstart = xstart->next;
xlen --;
}
if(xstart != NULL){
xindex = xstart;
while (xindex->next != NULL){
if(xindex->next->index < min){
xindex->next = xindex->next->next;
xlen --;
}
xindex = xindex->next;
}
}
//printx();
}
void computemin(){
if(xstart == NULL) return;
if(xbase != MAX && v[xstart->index] <= v[xbase]) return;
node *xindex;
xbase = xmin = xmax = xstart->index;
xindex = xstart;
while (xindex != NULL){
if(xindex->index > xmax){
xmax = xindex->index;
}
if(xindex->index < xmin){
xmin = xindex->index;
}
xindex = xindex->next;
}
}
void read(){
ifstream fi("secventa.in");
fi >> n;
fi >> k;
for (int i = 0; i < n; i ++){
fi >> v[i];
}
fi.close();
}
void write(){
ofstream fo("secventa.out");
fo << xmin+1 << " " << xmax+1 << " " << v[xbase];
fo.close();
}
void compute(){
int i = 0, j;
xstart = NULL;
xlen = 0;
while(i < n){
removemin();
for(j = xlen; j < k; j ++){
insertion(i);
i ++;
}
computemin();
}
//print();
}
int main(void){
read();
compute();
write();
return 0;
}