Submission #432065

#	Time	Username	Problem	Language	Result	Execution time	Memory
432065		LouayFarah	Arranging Shoes (IOI19_shoes)	C++14	30 / 100	1082 ms	5156 KiB

shoes

#include "bits/stdc++.h"
#include "shoes.h"
using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long int


ll cost(vector<int> &temp, int i, int p, int n)
{
    ll c = 0;
    while(p>i)
    {
        swap(temp[p], temp[p-1]);
        c++;
        p--;
    }

    int target = -temp[i];

    int j = 0;
    for(j = i; j<2*n; j++)
    {
        if(temp[j]==target)
            break;
    }
    while(j>i+1)
    {
        swap(temp[j], temp[j-1]);
        c++;
        j--;
    }

    return c;
}

ll count_swaps(vector<int> s)
{
    int n = (int)s.size()/2;

    ll res = 0;
    for(int i = 0; i<2*n; i+=2)
    {
        if(s[i]+s[i+1]==0&&s[i]<s[i+1])
            continue;

        vector<int> pos;
        for(int j = i; j<2*n; j++)
        {
            if(s[j]<0)
                pos.pb(j);
        }

        vector<int> cp = s;
        ll mini = 1e18;
        for(auto p: pos)
        {
            vector<int> temp = s;
            ll c = cost(temp, i, p, n);
            if(c<mini)
            {
                cp = temp;
                mini = c;
            }
        }
        s = cp;
        res+=mini;
    }

    return res;
}

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