Cod sursa(job #2642129)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 13 august 2020 19:10:48
Problema Barman Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#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 abs(int x , int y)
{
    if(x > y)
        swap(x , y);
    return min(y - x , x + n - y);
}
int main()
{
    freopen("barman.in" , "r" , stdin);
    freopen("barman.out" , "w" , stdout);
    int i , j , k , l , cnt , minim , sum;
    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 = 1 ; i <= cnt ; i ++)
        sort(T1[i].begin() , T1[i].end());
    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);
        for(j = 1 ; j <= cnt ; j ++)
            sort(T2[j].begin() , T2[j].end());
        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 ++)
                for(l = 0 ; l < T2[j].size() ; l ++)
                    if(aux[k] == T2[j][l])
                    {
                        aux.erase(aux.begin() + k);
                        T2[j].erase(T2[j].begin() + l);
                        k --;
                        l --;
                        break;
                    }
            for(k = 0 ; k < aux.size() ; k ++)
                sum += abs(aux[k] - T2[j][k]) + 20;
        }
        minim = min(minim , sum);
    }
    printf("%d\n" , minim);
    return 0;
}