Cod sursa(job #2040683)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 16 octombrie 2017 10:47:09
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

#define x first
#define y second

#define ll long long

#define MAXN 600

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

bool viz[MAXN + 1], ok[MAXN + 1];
int v[MAXN + 1], c[MAXN + 1], start[MAXN + 1], sef;
vector <int> g[MAXN + 1];
pair <int, int> a[MAXN + 1];

inline bool interior(int l, int r, int x) {
    if (l <= r) return (l <= x && x <= r);
    else return (x <= r || x >= l);
}

inline ll calc(int n, int k) {
    int l = start[k], r = start[k % sef + 1] - 1;
    if (r == 0) r = n;
    ll sum = 0;

    for (int i = 0; i < (int)g[k].size(); i++)
        if (interior(l, r, g[k][i])) ok[i] = 1, viz[g[k][i]] = 1;
        else ok[i] = 0;

    if (l <= r) {
        int p = l;
        for (int i = 0; i < (int)g[k].size(); i++) if (ok[i] == 0) {
            while (viz[p]) p++;
            sum += abs(g[k][i] - p) + 20;
            p++;
        }
    } else {
        int p = 1;
        for (int i = 0; i < (int)g[k].size(); i++) if (ok[i] == 0) {
            if (p <= r) {
                while (p <= r && viz[p]) p++;
                if (p > r) p = l;
                while (viz[p]) p++;
            } else while (viz[p]) p++;
            sum += abs(g[k][i] - p) + 20;
            if (p == r) p = l;
            else p++;
        }
    }

    for (int i = 0; i < (int)g[k].size(); i++)
        if (ok[i])
            ok[i] = 0, viz[g[k][i]] = 0;

    return sum;
}

int main() {
    int n;
    fin >> n;

    for (int i = 1; i <= n; i++)
        fin >> a[i].x, a[i].y = i;

    sort(a + 1, a + n + 1);

    int k = 0;
    for (int i = 1; i <= n; i++)
        if (a[i].x == a[i - 1].x) v[i] = k;
        else v[i] = ++k;

    for (int i = 1; i <= n; i++)
        c[v[i]] = a[i].x;

    for (int i = 1; i <= n; i++)
        if (v[i] > v[i - 1])
            start[v[i]] = i;

    for (int i = 1; i <= n; i++)
        g[v[i]].push_back(a[i].y);

    for (int i = 1; i <= k; i++)
        sort(g[i].begin(), g[i].end());

    sef = k;
    ll ans = -1;
    for (int i = 0; i < n; i++) {
        ll sum = 0;
        for (int j = 1; j <= k; j++)
            sum += calc(n, j);

        if (ans == -1 || sum < ans)
            ans = sum;

        for (int j = 0; j < n; j++)
            v[j] = v[j + 1];
        v[n] = v[0];
        for (int j = 1; j <= k; j++) {
            start[j]--;
            if (start[j] == 0)
                start[j] = n;
        }
    }

    fout << ans;

    return 0;
}