Cod sursa(job #2642121)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 13 august 2020 18:52:00
Problema Barman Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define nod first
#define cost second
using namespace std;
const int NMAX = 600;
const int INF = 2.e9;
typedef pair <int , int> muchii;
vector <int> T1[NMAX + 5];
int v[NMAX + 5] , n;
muchii s[2 * NMAX + 5];
int cmp(muchii a , muchii b)
{
    return a.cost < b.cost;
}
int main()
{
    freopen("barman.in" , "r" , stdin);
    freopen("barman.out" , "w" , stdout);
    int i , j , k , cnt , minim , sum , l;
    scanf("%d" , &n);
    for(i = 0 ; i < n ; i ++)
    {
        scanf("%d" , &v[i]);
        s[i] = {i , v[i]};
    }
    sort(s , s + n , cmp);
    cnt = 1;
    for(i = 0 ; i < n ; i ++)
    {
        if(i > 0 && s[i].cost != s[i - 1].cost)
            cnt ++;
        v[s[i].nod] = cnt;
        T1[cnt].push_back(s[i].nod);
    }
    for(i = n ; i < 2 * n ; i ++)
    {
        s[i].cost = v[s[i - n].nod];
        s[i - n].cost = v[s[i - n].nod];
    }
    minim = INF;
    for(i = 0 ; i < n ; i ++)
    {
        vector <int> T2[NMAX + 5];
        for(j = i ; j < n + i ; j ++)
            T2[s[j].cost].push_back(j - i);
        sum = 0;
        for(j = 1 ; j <= cnt ; j ++)
        {
            vector <int> aux;
            for(k = 0 ; k < T1[j].size() ; k ++)
                aux.push_back(T1[j][k]);
            for(k = 0 ; k < aux.size() ; k ++)
                if(aux[k] == T2[j][k])
                {
                    aux.erase(aux.begin() + k);
                    T2[j].erase(T2[j].begin() + k);
                    k --;
                }
            int f[NMAX + 5];
            memset(f , 0 , sizeof(f));
            for(k = 0 ; k < T2[j].size() ; k ++)
                f[T2[j][k]] = 1;
            for(k = 0 ; k < aux.size() ; k ++)
                for(l = 0 ; l < n ; l ++)
                    if(f[l])
                    {
                        sum += abs(aux[k] - l) + 20;
                        f[l] = 0;
                        break;
                    }
        }
        minim = min(minim , sum);
    }
    printf("%d\n" , minim);
    return 0;
}