Submission #147284

#	Time	Username	Problem	Language	Result	Execution time	Memory
147284		joylintp	Arranging Shoes (IOI19_shoes)	C++14	85 / 100	1045 ms	3956 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"

using namespace std;

long long count_swaps(vector<int> s)
{
    long long n = s.size(), ret = 0;

    bool sub2 = true, sub3 = true;
    for (int i = 0; i < n && sub2; i++)
        if (abs(s[i]) != abs(s[0]))
            sub2 = false;

    for (int i = 0; i < n / 2 && sub3; i++)
        if (s[i] > 0 || -s[i] != s[i + n / 2])
            sub3 = false;

    if (sub2)
    {
        vector<int> vv, ww;
        for (int i = 0; i < n; i++)
            if (i % 2 == 0 && s[i] > 0)
                vv.push_back(i);
            else if (i % 2 && s[i] < 0)
                ww.push_back(i);

        for (int i = 0; i < (int)vv.size(); i++)
            ret += abs(vv[i] - ww[i]);
        return ret;
    }

    if (sub3)
    {
        n /= 2;
        return (n - 1) * n / 2;
    }


    for (int i = 0; i < n; i++)
    {
        int j;
        if (i % 2 == 0)
            for (j = i; s[j] != -abs(s[i]); j++);
        else
            for (j = i; s[j] != -s[i - 1]; j++);

        ret += j - i;
        int t = s[j];
        for (int k = j - 1; k >= i; k--)
            s[k + 1] = s[k];
        s[i] = t;
    }

	return ret;
}

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