Cod sursa(job #978166)

Utilizator danlexDan Alexandru danlex Data 28 iulie 2013 01:46:46
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#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;
}