제출 #906246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
906246		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	65 ms	8244 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()/2;
    map<ll, ll> cnt;
    for (auto x: s) cnt[abs(x)]++;

	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) {
        // subtask 3; thinking 
    }
    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;
}

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