Cod sursa(job #975665)

Utilizator danlexDan Alexandru danlex Data 21 iulie 2013 00:05:09
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>
using namespace std;

int k, n, v[500001], x[500001], xlen, xbase, xmin, xmax;

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(){
	int i;
	for(i = 0; i < xlen; i ++){
        cout << x[i] << " ";
    }
    cout << endl;

    for(i = 0; i < xlen; i ++){
        cout << v[x[i]] << " ";
    }
    cout << endl << endl;
}

void insertion(int p){
	int i, j;
	for(i = 0; i < xlen; i ++){
		if(v[x[i]] > v[p]){
			for(j = xlen - 1; j >= i; j --){
				x[j+1] = x[j];
			}
			break;
		}
	}
	x[i] = p;
	xlen ++;
	
	//printx();
}

void removemin(){
	int min, i, ylen, y[500001];
	min = x[0];
	ylen = 0;
	for(i = 0; i < xlen; i++){
		if(x[i] > min){
			y[ylen] = x[i];
			ylen ++;
		}
	}
	xlen = ylen;
	for(i = 0; i < xlen; i ++){
		x[i] = y[i];
	}
	//printx();
}

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, j;
	xlen = 0;
	for(i = 0; i < k; i ++){
		insertion(i);
	}
	xbase = x[0];
	xmin = x[0];
	xmax = x[0];
	for(j = 0; j < xlen; j ++){
		if(x[j] > xmax){
			xmax = x[j];
		}
		if(x[j] < xmin){
			xmin = x[j];
		}
	}

	while(i < n){
		removemin();
		for(j = xlen; j < k; j ++){
			insertion(i);
			i ++;
		}
		if(v[x[0]] > v[xmin]){
			xbase = x[0];
			xmin = x[0];
    		xmax = x[0];
    		for(j = 0; j < xlen; j ++){
        		if(x[j] > xmax){
            		xmax = x[j];
        		}
        		if(x[j] < xmin){
            		xmin = x[j];
        		}
    		}
		}
	}
	
	//print();
}

int main(void){
    read();
    compute();
	write();
    return 0;
}