Cod sursa(job #824531)

Utilizator crushackPopescu Silviu crushack Data 26 noiembrie 2012 18:39:39
Problema Barman Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <algorithm>
#define NMax 610
using namespace std;

const char IN[]="barman.in",OUT[]="barman.out";

struct interval{
	int x,y;
} vec[NMax],t[NMax],p[NMax];

int N,L,Rez=(1<<30);
bool b[NMax];
int v[NMax],a[NMax],s[NMax];

int dist(int x,int y)
{
	if (x>y) swap(x,y);
	return min(y-x,N-y+x);
}

int search(int x)
{
	int i,step;
	for (step=1;step<=L;step<<=1);
	for (i=0;step;step>>=1)
		if (i+step<=L && a[i+step]<=x)
			i+=step;
	return i;
}

void rotate()
{
	int i,x;
	x=v[1];
	for (i=2;i<=N;++i) v[i-1]=v[i];
	v[N]=x;
}

int solve()
{
	int i,ret=0;
	for (i=1;i<=N;++i) b[i]=false;

	for (i=1;i<=N;++i)
		if (v[i]==s[i])
			b[i]=true;

	for (i=1;i<=N;++i) if (v[i]!=s[i])
	{
		for (;b[vec[v[i]].x];++vec[v[i]].x);
		for (;b[vec[v[i]].y];--vec[v[i]].y);

		if (vec[v[i]].x<=i && i<=vec[v[i]].y)
			{b[i]=true;continue;}
		if (dist(i,vec[v[i]].x)<dist(i,vec[v[i]].y) )
			ret+=20+dist(i,vec[v[i]].x),
			b[vec[v[i]].x]=true;
		else
			ret+=20+dist(i,vec[v[i]].y),
			b[vec[v[i]].y]=true;

		for (;b[vec[v[i]].x];++vec[v[i]].x);
		for (;b[vec[v[i]].y];--vec[v[i]].y);
	}
	return ret;
}

int main()
{
	int i;
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	for (i=1;i<=N;++i) scanf("%d",v+i),a[i]=v[i];
	fclose(stdin);

	sort(a+1,a+N+1);
	L=unique(a+1,a+N+1)-a-1;

	for (i=1;i<=N;++i)
		v[i]=search(v[i]),s[i]=v[i];

	sort(s+1,s+N+1);

	for (int j=1;j<=N;++j)
	{
		if (j!=1) rotate();
		for (i=1;i<=N;++i)
			if (s[i]!=s[i-1]) vec[s[i]].x=vec[s[i]].y=i;
			else vec[s[i]].y=i;
		Rez=min(Rez,solve());
	}

	freopen(OUT,"w",stdout);
	printf("%d\n",Rez);
	fclose(stdout);

	return 0;
}