Submission #906243

#	Time	Username	Problem	Language	Result	Execution time	Memory
906243		bobbilyking	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	61 ms	9404 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define F(i, l, r) for (ll i = l; i < (r); ++i)
using vl = vector<ll>;
#define A(a) (a).begin(), (a).end()

long long count_swaps(std::vector<int> s) {
    ll n = s.size();
    map<ll, ll> cnt;
    F(i, 0, s.size()) cnt[abs(s[i])]++;
	if (n <= 8) {
        vl perm; for (auto [k, v]: cnt) {
            v/=2;
            while(v-- ) perm.push_back(k);
        }
        sort(A(perm));
        ll ans = 1e9;
        do {
            vl ts(A(s));
            ll tans = 0;
            for (auto v: perm) {
                auto x = find(A(ts), -v);
                tans += x - ts.begin();
                ts.erase(x);
                x = find(A(ts), v);
                tans += x - ts.begin();
                ts.erase(x);
            }
            ans = min(ans, tans);

        } while (next_permutation(A(perm)));
        return ans;
    }
    if (cnt.size() == 1) {

    }
    bool subtask4 = 1;
    F(i, 0, n) {
        subtask4 &= abs(s[i]) == abs(s[i + n/2]);
        subtask4 &= s[i] < 0;
        subtask4 &= s[i + n/2] > 0;
    }
    if (subtask4) return n * (n-1)/2;
    
    return -1;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:5:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define F(i, l, r) for (ll i = l; i < (r); ++i)
      |                                     ^
shoes.cpp:12:5: note: in expansion of macro 'F'
   12 |     F(i, 0, s.size()) cnt[abs(s[i])]++;
      |     ^

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