Cod sursa(job #1313574)

Utilizator wGEORGEWGeorge Cioti wGEORGEW Data 10 ianuarie 2015 20:49:45
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <deque>
#include <limits>
 
using namespace std;
 
int main()
{
    ifstream cin("barman.in");
    ofstream cout("barman.out");
    int n;
    cin >> n;
    vector<int> v(n);
    set<int> s;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        s.insert(v[i]);
    }
 
    vector<int> sov(s.begin(), s.end());
    vector<int> num(s.size(),0);
    vector< vector<int> > who(num.size());
    vector< pair<int, int> > a;
    for (int i = 0; i < n; i++) {
        v[i] = lower_bound(sov.begin(), sov.end(), v[i]) - sov.begin();
        num[v[i]]++;
        who[v[i]].push_back(i);
    }
 
    a.push_back({ 0, num[0] - 1 });
    for (int i = 1; i < (int)num.size(); i++) {
        num[i] += num[i - 1];
        a.push_back({ num[i - 1], num[i] - 1 });
    }
 
    auto check = [&](const int& val,const int& j) {
        if (a[val].first <= a[val].second) {
            return (a[val].first <= j && j <= a[val].second);
        }
 
        return (j <= a[val].second || a[val].first <= j);
    };
          
 
    int ans = numeric_limits<int>::max();
    for (int i = 0; i < n; i++) {
        int ret = 0;
        vector<bool> use(n,false);
        vector< vector<int> > w(num.size());
        for (int j = 0; j < n; j++) {
            if (check(v[j], j) == false) {
                w[v[j]].push_back(j);
            } else {
                use[j] = true;
            }
        }
 
        for (int j = 0; j < (int)a.size(); j++) {
            if (a[j].first <= a[j].second) {
                for (int k = a[j].first, z = 0; k <= a[j].second; k++) {
                    if (!use[k]) {
                        ret += 20 + abs(k - w[j][z++]);
                    }
                }
            } else {
                int z = 0;
                 
                for (int k = 0; k <= a[j].second; k++) {
                    if (!use[k]) {
                        ret += 20 + abs(k - w[j][z++]);
                    }
                }
             
                for (int k = a[j].first; k < n; k++) {
                    if (!use[k]) {
                        ret += 20 + abs(k - w[j][z++]);
                    }
                }
                 
 
            }
        }
 
        for (int j = 0; j < (int)a.size(); j++) {
            a[j].first++;
            a[j].second++;
            if (a[j].first == n) a[j].first = 0;
            if (a[j].second == n) a[j].second = 0;
        }
        ans = min(ans, ret);
    }
 
 
    cout << ans;
    return 0;
}