Cod sursa(job #1223142)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 25 august 2014 15:50:58
Problema Barman Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int knmax = 605;

int n, gv[knmax], srt[knmax];

void get_positions(){
  for(int i = 0; i < n; ++i)
    srt[i] = gv[i];
  sort(srt, srt + n);

  int aux[knmax] = {0};
  for(int i = 1; i < n; ++i)
    if(srt[i] != srt[i - 1])
      aux[i] = aux[i - 1] + 1;
    else
      aux[i] = aux[i - 1];

  for(int i = 0; i < n; ++i){
    int lef = 0, rai = n - 1, mid, val = gv[i];

    while(lef <= rai){
      mid = (lef + rai) / 2;
      if(srt[mid] > val)
        rai = mid - 1;
      else if(srt[mid] < val)
        lef = mid + 1;
      else{
        gv[i] = aux[mid];
        break;
      }
    }
  }

  for(int i = 0; i < n; ++i)
    srt[i] = gv[i];
  sort(srt, srt + n);
}

int dist(int x, int y){
  if(x < y)
    return x + 1 + n - y;
  return x - y;
}

int start(int s){
  int ind = s, i = 0, rval = 0;
  do{
    int num = 1, x = srt[i], lt = i;
    ++i;
    while(i < n && srt[i] == srt[i - 1]){
      ++i;
      ++num;
    }

    vector<int> oc;
    for(int j = ind; j < i + ind - lt; ++j)
      if(gv[j % n] != x)
        oc.push_back(j % n);

    vector<int> lef, rai;
    int u = (i + ind - lt) % n;
    while(u != ind){
      if(gv[u] == x)
        rai.push_back(u);
      u = (u + 1) % n;
    }

    int p;
    for(int j = 0; j < rai.size(); ++j)
      rval += 20 + dist(rai[j], oc[j]);
    p = rval;
    while(!rai.empty()){
      p -= dist(rai.back(), oc[lef.size()]);
      lef.push_back(rai.back());
      p += dist(oc[lef.size() - 1], lef.back());
      rai.pop_back();
      rval = min(rval, p);
    }

    ind = (ind + num) % n;
  }while(ind != s);

  return rval;
}

int main(){
  ifstream in("barman.in");
  ofstream out("barman.out");

  in >> n;
  for(int i = 0; i < n; ++i)
    in >> gv[i];

  get_positions();

  int ans = 2e9;
  for(int i = 0; i < n; ++i)
    ans = min(ans, start(i));

  out << ans;

  return 0;
}