Cod sursa(job #1402444)

Utilizator victor1Vasilescu Victor victor1 Data 26 martie 2015 16:30:11
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("barman.in");
ofstream g("barman.out");
const int NMax = 605;
int N;
int Min=0x3f3f3f3f;
pair <int,int> Array[NMax];
int V[NMax];
vector <int> Poz[NMax];
int Ind[NMax];
void Read()
{
    f>>N;
    for(int i=1;i<=N;i++)
        f>>Array[i].first,Array[i].second=i,V[i]=Array[i].first;
}
inline bool compare(pair <int,int> a,pair <int,int> b)
{
    return a.second<b.second;
}
void buildArray()
{
    sort(V+1,V+N+1);
    sort(Array+1,Array+N+1);
    int ind=0;
    for(int i=1;i<=N;i++)
    {
        if(V[i]!=V[i-1])
            Array[i].first=++ind;
        else
            Array[i].first=ind;
    }
    for(int i=1;i<=N;i++)
        V[i]=Array[i].first;
    sort(Array+1,Array+N+1,compare);
}
inline int mod(int x)
{
    return max(x,-x);
}
void Solve()
{
    int result=0;
    for(int i=1;i<=N;i++)
    {
        if(Array[i].first!=V[i])
            Poz[V[i]].push_back(i);
    }
    int aux=0;
    for(int i=1;i<=N;i++)
    {
        int val=Array[i].first;
        if(Array[i].first==V[i])
            continue;
        ++aux;
        result+=mod(i-Poz[val][Ind[val]]);
        ++Ind[val];
    }
    Min=min(Min,result+aux*20);
}

int main()
{
    Read();
    buildArray();
    for(int i=1;i<=N;i++)
    {
        Solve();
        rotate(V+1,V+2,V+N+1);
        for(int i=1;i<=N;i++)
        {
            Poz[i].clear();
            Ind[i]=0;
        }
    }
    g<<Min<<"\n";
    return 0;
}