Cod sursa(job #2725040)

Utilizator PetyAlexandru Peticaru Pety Data 18 martie 2021 12:24:20
Problema Barman Scor 0
Compilator cpp-64 Status done
Runda simularesimulare Marime 1.21 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];
vector<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;
  for (int i = 1; i <= n; i++)
    v2[i] = lower_bound(v2 + 1, v2 + n + 1, v2[i]) - v2;
  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]].push_back(j);
  }
  for (int i = 1; i <= n; i++) {
    
    int ans = 0, cnt = 0;
    for (int j = 1; j <= n; j++) {
      if (v[j] != v2[j + i - 1]) {
        int x = lower_bound(poz[v2[j + i - 1]].begin(), poz[v2[j + i - 1]].end(), j) - poz[v2[j + i - 1]].begin() - 1;
        if (x == -1) {
          ans += abs(poz[v2[j + i - 1]][0] - j);
        }
        else 
          ans += abs(poz[v2[j + i - 1]][x] - j); 
        cnt++;
      }
    }
    sol = min(sol, ans + 20 * cnt);
  }
  fout << sol;
  return 0;
}