Submission #143833

#	Time	Username	Problem	Language	Result	Execution time	Memory
143833		stoyan_malinin	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	34 ms	3680 KiB

shoes

#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

const int MAXN = 1005;

int bestLeft[MAXN], bestRight[MAXN];

int moveElement(int i, int j, vector <int> &s)
{
    int cnt = 0;
    while(j>i)
    {
        cnt++;

        swap(s[j-1], s[j]);
        j--;
    }

    return cnt;
}

int calcValue(int num, int index)
{
    int sum = (bestLeft[num] - index) + (bestRight[num] - (index+1));
    if(bestLeft[num]>bestRight[num]) sum++;

    return sum;
}

long long count_swaps(vector <int> s)
{
    int answer = 0;
    for(int index = 0;index<s.size();index+=2)
    {
        memset(bestLeft, -1, sizeof(bestLeft));

        for(int i = s.size()-1;i>=index;i--)
        {
            if(s[i]<0) bestLeft[ -s[i] ] = i;
            else bestRight[ s[i] ] = i;
        }

        int bestIndex = -1;
        for(int i = 1;i<=s.size()/2;i++)
        {
            if(bestLeft[i]==-1) continue;

            if(bestIndex==-1) bestIndex = i;
            else if(calcValue(bestIndex, index)>calcValue(i, index))
            {
                bestIndex = i;
            }
        }
        if(bestLeft[bestIndex]>bestRight[bestIndex]) bestRight[bestIndex]++;

        //cout << "   " << bestIndex << '\n';

        answer += moveElement(index, bestLeft[bestIndex], s);
        answer += moveElement(index+1, bestRight[bestIndex], s);
    }

    //for(int i = 0;i<s.size();i++) cout << s[i] << " ";
    //cout << '\n';

    return answer;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:36:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int index = 0;index<s.size();index+=2)
                       ~~~~~^~~~~~~~~
shoes.cpp:47:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1;i<=s.size()/2;i++)
                       ~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15