Cod sursa(job #2650221)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 17 septembrie 2020 19:18:17
Problema Secv Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
//
//  main.cpp
//  secv
//
//  Created by Eusebiu Rares on 17/09/2020.
//  Copyright © 2020 Eusebiu Rares. All rights reserved.
//

#include <iostream>
#include "fstream"
#include "unordered_map"
#include "vector"

std::fstream input ("secv.in", std::ios::in) ;
std::fstream output ("secv.out", std::ios::out) ;

const int MV = 50 ;

int v[MV + 1] ;

void normalise(int n) {
	std::vector<int> temp(n + 1) ;
	std::unordered_map<int, int> resp ;
	for (int i = 1 ; i <= n ; ++ i) {
		temp[i] = v[i] ;
	}
	std::sort(begin(temp), end(temp)) ;
	int var(1) ;
	for (int i = 1 ; i <= n ; ++ i) {
		if (temp[i] != temp[i - 1]) {
			resp[temp[i]] = var ++ ;
		}
	}
	for (int i = 1 ; i <= n ; ++ i) {
		v[i] = resp[v[i]] ;
	}
}

int lastSeen[MV + 1] ;
int startPoint[MV + 1] ;

int main(int argc, const char * argv[]) {
	int n ; input >> n ;
	for (int i = 1 ; i <= n ; ++ i) {
		input >> v[i] ;
	}
	normalise(n) ;
	int ans(1e9), last(v[n]) ;
	for (int i = 1 ; i <= n ; ++ i) {
		if (v[i] == 1) {
			startPoint[i] = i ;
			lastSeen[v[i]] = i ;
		} else if (v[i] < last){
			if (lastSeen[v[i] - 1]) {
				startPoint[i] = startPoint[lastSeen[v[i] - 1]] ;
				lastSeen[v[i]] = i ;
			}
		} else {
			if (lastSeen[last - 1]) {
				startPoint[i] = startPoint[lastSeen[last - 1]] ;
				lastSeen[v[i]] = i ;
				ans = std::min(ans, i - startPoint[i] + 1) ;
			}
		}
	}
	output << ans ;
}