Cod sursa(job #2725050)

Utilizator PetyAlexandru Peticaru Pety Data 18 martie 2021 12:44:09
Problema Barman Scor 100
Compilator cpp-64 Status done
Runda simularesimulare Marime 1.43 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const int N  = 1202;

ifstream fin ("barman.in");
ofstream fout ("barman.out");

int n, v[N], v2[N], aux[N];
set<int>poz[N];

int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++) {
    fin >> v[i];
    v2[i] = v[i];
  }
  sort(v2 + 1, v2 + n + 1);
  for (int i = 1; i <= n; i++) {
    v[i] = lower_bound(v2 + 1, v2 + n + 1, v[i]) - v2;
    aux[i] = v2[i];
  }
  for (int i = 1; i <= n; i++)
    v2[i] = lower_bound(aux + 1, aux + n + 1, v2[i]) - aux;
  for (int i = 1; i <= n; i++)
    v2[i + n] = v2[i];
  int sol = INF;
  for (int j = 1; j <= n; j++) {
    poz[v[j]].insert(j);
  }
  for (int i = 1; i <= n; i++) {    
    int ans = 0, cnt = 0;
    for (int j = 1; j <= n; j++)
      if (v[j] == v2[i + j - 1])
        poz[v[j]].erase(j);
    for (int j = 1; j <= n; j++) {
      if (v[j] != v2[j + i - 1]) {
        auto x = poz[v2[i + j - 1]].lower_bound(j);
        if (x == poz[v2[i + j - 1]].begin()) {
          ans += abs(*x - j);
          poz[v2[i + j - 1]].erase(x);
        }
        else { 
          x--;
          ans += abs(*x - j); 
          poz[v2[i + j - 1]].erase(x);
        }
        cnt++;
      }
    }
    for (int j = 1; j <= n; j++)
      poz[v[j]].insert(j);
    sol = min(sol, ans + 20 * cnt);
  }
  fout << sol;
  return 0;
}