Submission #724290

#	Time	Username	Problem	Language	Result	Execution time	Memory
724290		PixelCat	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	24 ms	13076 KiB

shoes

#include "shoes.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100010;

vector<int> l[MAXN];
vector<int> r[MAXN];

int solve1(std::vector<int32_t> s) {
    int n = sz(s) / 2;
    For(i, 0, n * 2 - 1) {
        if(s[i] < 0) l[-s[i]].eb(i);
        else r[s[i]].eb(i);
    }
    vector<pii> owo;
    int add = 0;
    For(siz, 1, n) {
        For(i, 0, sz(l[siz]) - 1) {
            int a = l[siz][i];
            int b = r[siz][i];
            if(a > b) {
                add++;
                swap(a, b);
            }
            owo.eb(a, b);
        }
    }
    int res = 10000;
    sort(all(owo));
    do {
        int cur = 0;
        int re = 0;
        for(auto &p:owo) {
            re += abs(p.F - cur) + abs(p.S - cur - 1);
            cur += 2;
        }
        res = min(res, re / 2 + add);
    } while(next_permutation(all(owo)));
    return res;
    // sort(all(owo), [&](pii a, pii b) {
    //     if(a.F < b.F && a.S < b.S) return true;
    //     return false;
    // });
    // int cur = 0;
    // int res = 0;
    // for(auto &p:owo) {
    //     res += abs(p.F - cur) + abs(p.S - cur - 1);
    //     cur += 2;
    // }
    // return res / 2 + add;
}

long long count_swaps(std::vector<int32_t> s) {
    int n = sz(s) / 2;
    assert(n <= 8);
    return solve1(s);
}

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