Submission #1011684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011684		u_suck_o	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1080 ms	3536 KiB

shoes

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

using namespace std;

long long count_swaps(vector<int> s) {
    long long ans = 0;
    long long n = s.size()/2;
    long long minloc[n+1][2];
    for (int p = 0; p < n; p++) {
        memset(minloc, 0x3f, sizeof minloc);
        for (long long i = 0; i < s.size(); i++) {
            if (s[i] < 0)
                minloc[-s[i]][0] = min(minloc[-s[i]][0], i);
            else
                minloc[s[i]][1] = min(minloc[s[i]][1], i);
        }
        long long mind = LONG_LONG_MAX, mini = -1;
        for (int i = 1; i <= n; i++) {
            long long d = minloc[i][0] + minloc[i][1] - 1;
            if (minloc[i][0] > minloc[i][1]) d += 1;
            if (d < mind) {
                mind = d;
                mini = i;
            }
        }
        ans += mind;
        s.erase(s.begin() + max(minloc[mini][0], minloc[mini][1]));
        s.erase(s.begin() + min(minloc[mini][0], minloc[mini][1]));
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:12:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for (long long i = 0; i < s.size(); 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