Cod sursa(job #463674)

Utilizator mgntMarius B mgnt Data 17 iunie 2010 01:50:49
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;

struct M
{
  int v, i;
  bool operator < (M const & o) { return ((v<o.v) || ((v==o.v) && (i<o.i))); }
};

int const maxn = 600; typedef int V[maxn]; typedef M W[maxn]; W a; V x, z, d;

int main()
{
  ifstream is("barman.in"); int n, i, k, f, g, s, l, r, m, j, q, e, y; is >> n;
  for (i=0; n>i; ++i) { is >> a[i].v; a[i].i=i; }
  make_heap(&a[0], &a[n]); sort_heap(&a[0], &a[n]);
  for (x[0]=i=k=0; n>i; ++i)
  { if ((0<i) && (a[i-1].v!=a[i].v)) { z[k]=i-1; ++k; x[k]=i; } }
  z[k]=n-1; ++k; f = maxn * (1+maxn);
  for (s=0; n>s; ++s)
  {
    for(i=g=0; k>i; ++i)
    {
      l = ((s+x[i])%n); r = ((s+z[i])%n); m=z[i]-x[i];
      for ( j=0; m>=j; ++j) { d[(l+j)%n]=0; }
      for ( j=0; m>=j; ++j) { d[a[x[i]+j].i]=1; }
      q=(l<=r) ? l : 0;
      for (j=0; m>=j; ++j)
      { e = a[x[i]+j].i;
        if ( ((l<=r) && ((l>e)||(r<e))) || ((l>r) && ((r<e)&&(e<l))) )
        {
          while (1 == d[q]) {q = (q==r)?l:(1+q); }
          y = (e-q); g += (20+((0<y)?y:(-y)));
          q = (q==r)?l:(1+q);
        }
      }
    }
    if (f>g) { f=g; }
  }
  ofstream os("barman.out"); os<<f<<endl; return 0;
}