Submission #418961

#	Time	Username	Problem	Language	Result	Execution time	Memory
418961		JediMaster11	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	32 ms	2640 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vint vector<int>
#define vll vector<long long>
#define fo(a, b, c) for (int a = b; a < (int)c; a++)
#define rfo(a, b, c) for (int a = b - 1; a >= (int)c; a--)
#define print(x) cout << x << "\n"

ll s2(vint s)
{

    ll count = 0;
    ll on, l, r;

    while (s.size() > 0)
    {

        on = abs(s[s.size() - 1]);
        l = s.size() - 1, r = s.size() - 1;

        rfo(i, s.size() - 1, 0)
        {

            if (abs(s[i]) == on)
            {

                if (s[i] > 0) // right
                {
                    r = i;
                }
                else
                {
                    l = i;
                }
                break;
            }
        }

        if (r < l)
        { // right must be moved
            count += abs((ll)s.size() - 1 - r);
            s.erase(s.begin() + l);
            s.erase(s.begin() + r);
        }
        else
        {

            count += abs((ll)s.size() - 2 - l);
            s.erase(s.begin() + r);
            s.erase(s.begin() + l);
        }
    }

    return count;
}
ll s3(vint s)
{

    int leftOn = 0;
    int rightOn = 1;
    ll sum = 0;

    fo(i, 0, s.size())
    {

        if (s[i] > 0) //right
        {
            sum += abs(i - rightOn);
            rightOn += 2;
        }
        else
        {
            sum += abs(i - leftOn);
            leftOn += 2;
        }
    }

    return sum / 2;
}
ll s4(vint s)
{

    ll n = (ll)s.size() / 2;

    return (n * n - n) / 2;
}

// s - the array of shoes, with -1 being left and 1 being right
ll count_swaps(vint s)
{

    if (s.size() == 2)
        return s[0] > 0 ? 1 : 0;

    int val = abs(s[0]);
    bool allSame = true;

    int n = s.size() / 2;
    bool halfed = true;
    fo(i, 0, n)
    {
        if (s[i] > 0 || s[i + n] < 0 || (s[i] + s[i + n] != 0))
        {
            halfed = false;
        }

        if (abs(s[i]) != val)
        {
            allSame = false;
        }

        // if(!allSame && !halfed) break;
    }

    if (allSame)
    {
        // print("s3");
        return s3(s);
    }

    if (halfed)
    {
        // print("s4");
        return s4(s);
    }

    // print("other");
    return s2(s);
}

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