Submission #419053

#	Time	Username	Problem	Language	Result	Execution time	Memory
419053		JediMaster11	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1093 ms	2632 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 = s[s.size() - 1];
        l = s.size() - 1, r = s.size() - 1;

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

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

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

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

            count += (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 || abs(s[i + n]) != 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);
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:97:10: warning: variable 'allSame' set but not used [-Wunused-but-set-variable]
   97 |     bool allSame = true;
      |          ^~~~~~~
shoes.cpp:100:10: warning: variable 'halfed' set but not used [-Wunused-but-set-variable]
  100 |     bool halfed = true;
      |          ^~~~~~

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