Cod sursa(job #1143656)

Utilizator ELHoriaHoria Cretescu ELHoria Data 15 martie 2014 20:11:19
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <deque>
#include <limits>

using namespace std;

int main()
{
	ifstream cin("barman.in");
	ofstream cout("barman.out");
	int n;
	cin >> n;
	vector<int> v(n);
	set<int> s;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		s.insert(v[i]);
	}

	vector<int> sov(s.begin(), s.end());
	vector<int> num(s.size(),0);
	vector< vector<int> > who(num.size());
	vector< pair<int, int> > a;
	for (int i = 0; i < n; i++) {
		v[i] = lower_bound(sov.begin(), sov.end(), v[i]) - sov.begin();
		num[v[i]]++;
		who[v[i]].push_back(i);
	}

	a.push_back({ 0, num[0] - 1 });
	for (int i = 1; i < (int)num.size(); i++) {
		num[i] += num[i - 1];
		a.push_back({ num[i - 1], num[i] - 1 });
	}

	auto check = [&](const int& val,const int& j) {
		if (a[val].first <= a[val].second) {
			return (a[val].first <= j && j <= a[val].second);
		}

		return (j <= a[val].second || a[val].first <= j);
	};
		 

	int ans = numeric_limits<int>::max();
	for (int i = 0; i < n; i++) {
		int ret = 0;
		vector<bool> use(n,false);
		vector< vector<int> > w(num.size());
		for (int j = 0; j < n; j++) {
			if (check(v[j], j) == false) {
				w[v[j]].push_back(j);
			} else {
				use[j] = true;
			}
		}

		for (int j = 0; j < (int)a.size(); j++) {
			if (a[j].first <= a[j].second) {
				for (int k = a[j].first, z = 0; k <= a[j].second; k++) {
					if (!use[k]) {
						ret += 20 + abs(k - w[j][z++]);
					}
				}
			} else {
				int z = 0;
				
				for (int k = 0; k <= a[j].second; k++) {
					if (!use[k]) {
						ret += 20 + abs(k - w[j][z++]);
					}
				}
			
				for (int k = a[j].first; k < n; k++) {
					if (!use[k]) {
						ret += 20 + abs(k - w[j][z++]);
					}
				}
				

			}
		}

		for (int j = 0; j < (int)a.size(); j++) {
			a[j].first++;
			a[j].second++;
			if (a[j].first == n) a[j].first = 0;
			if (a[j].second == n) a[j].second = 0;
		}
		ans = min(ans, ret);
	}


	cout << ans;
	return 0;
}