Cod sursa(job #771581)

Utilizator darrenRares Buhai darren Data 26 iulie 2012 14:17:11
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int A[602], B[602], C[602];
int fr[602], wh[602];
bool put[602], done[602];
int pos[602], result = 0x3f3f3f3f;
vector<int> V[2][602];

class compare
{
	public: inline bool operator () (const int& i1, const int& i2)
	{
		if (A[i1] != A[i2])
			return A[i1] < A[i2];
		return i1 < i2;
	}
};

inline int mabs(const int& x)
{
	return (x < 0 ? -x : x);
}
inline int real(const int& x, const int& y)
{
	return (x + y - 1 > N ? x + y - 1 - N : x + y - 1);
}

int main()
{
	ifstream fin("barman.in");
	ofstream fout("barman.out");
	
	fin >> N;
	for (int i = 1; i <= N; ++i)
	{
		fin >> A[i];
		pos[i] = i;
	}
	sort(pos + 1, pos + N + 1, compare());
	
	int now = 0;
	for (int i = 1; i <= N; ++i)
	{
		++now;
		while (i < N && A[pos[i]] == A[pos[i + 1]])
		{
			A[pos[i]] = now;
			++i;
		}
		A[pos[i]] = now;
	}
	
	for (int i = 1; i <= N; ++i)
		++fr[A[i]];
	for (int i = 1; i <= N; ++i)
		fr[i] += fr[i - 1];
	
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
			wh[j] = fr[j - 1] + 1;
		
		for (int j = i; j <= N; ++j)
			B[j - i + 1] = A[j];
		for (int j = 1; j < i; ++j)
			B[N - i + 1 + j] = A[j];
		
		memset(put, 0, sizeof(put));
		memset(done, 0, sizeof(done));
		for (int j = 1; j <= N; ++j)
			if (wh[B[j]] <= j && j <= fr[B[j]])
			{
				put[j] = true;
				done[j] = true;
			}
		
		int resultnow = 0;
		for (int j = 1; j <= N; ++j)
		{
			if (!done[j])
			{
				resultnow += 20;
				V[0][B[j]].push_back(real(j, i));
			}
			for (int k = wh[j]; k <= fr[j]; ++k)
				if (!put[k])
					V[1][j].push_back(real(k, i));
		}
		
		for (int j = 1; j <= N; ++j)
		{
			sort(V[0][j].begin(), V[0][j].end());
			sort(V[1][j].begin(), V[1][j].end());
			
			while (!V[0][j].empty() && !V[1][j].empty())
			{
				resultnow += mabs(V[0][j].back() - V[1][j].back());
				V[0][j].pop_back();
				V[1][j].pop_back();
			}
		}
		
		result = min(result, resultnow);
	}
	
	fout << result << '\n';
	
	fin.close();
	fout.close();
}