Cod sursa(job #786046)

Utilizator dogDaysAreOverAndreea Gheorghe dogDaysAreOver Data 10 septembrie 2012 13:50:21
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
//============================================================================
// Name        : COding.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <stack>
#include <climits>

using namespace std;

struct elementInfo{
	int position;
	int value;
};

void put_into_vector( ifstream& ifs, vector<int>& v )
{
	string s;
	getline( ifs, s );
	istringstream iss( s );
	// not the fastest method ...
	copy( istream_iterator<int>( iss ), istream_iterator<int>(), back_inserter( v ) );
}

void process(char* filePath){
	ifstream indata;
	stack<struct elementInfo> orderedElements;

	indata.open(filePath);
	if(!indata){
		cerr << "Error: file could not be opened" <<endl;
		exit(1);
	}

	vector<int> numbers;
	put_into_vector(indata , numbers);
	int N = numbers[0];
	int K = numbers[1];
	int length = N-K+1;

	vector<int> secv;
	put_into_vector(indata , secv);

	for (int index = 0; index < length; index ++){
//		cout << "iteration " << index << endl;

		if(index == 0)
			for(int i = index; i< index + K; i ++ ){
				// check whether the current element is smaller
				//	than the last element in the stack
				while(!orderedElements.empty() &&
						secv[i] < orderedElements.top().value
				){
//					cout << "removing " << orderedElements.top().value << endl;
					orderedElements.pop(); // remove the last element

				}

				struct elementInfo newStruct;
				newStruct.value = secv[i];
				newStruct.position = i;

				orderedElements.push(newStruct);
//				cout <<" adding element " << secv[i] << endl;
			}
		else{
			int location =  K + index - 1;
//			cout << "Index " << index << " Stack size " << orderedElements.size() << endl;

			// check whether the current element is smaller
			//	than the last element in the stack
			while(!orderedElements.empty() &&
					secv[location] < orderedElements.top().value
			){
				if(orderedElements.top().position <= index)
					break;
//				cout << "removing " << orderedElements.top().value << endl;
				orderedElements.pop(); // remove the last element

			}

			struct elementInfo newStruct;
			newStruct.value = secv[location];
			newStruct.position = location;

			orderedElements.push(newStruct);
//			cout <<" adding element " << secv[location] << endl;
		}


//		cout <<endl;
	}

	int minStartPos = 0;
	struct elementInfo minEl;
	minEl.value = INT_MIN;
	minEl.position = 0;

	while(!orderedElements.empty()){
		struct elementInfo element = orderedElements.top();

		if(element.position > N -K +1){
			orderedElements.pop();
			continue;
		}

		if (element.value > minEl.value){
			minEl.value = element.value;
			minEl.position = element.position;
		}

		orderedElements.pop();
	}

//	cout << endl;

	int minValue = minEl.value;
	int start = minEl.position + 1;
	int end = minEl.position + K;
	cout << minValue << " " << start << " " << end << endl;

}

int main(int argc, char* argv[]) {

	if (argc != 2){
		cout << "Incorrect number of arguments"<< endl;
		exit(1);
	}

	process(argv[1]);

	return 0;
}