Submission #670598

#	Time	Username	Problem	Language	Result	Execution time	Memory
670598		shrimb	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	25 ms	15300 KiB

shoes

#include "shoes.h"
#include"bits/stdc++.h"
using namespace std;


int N;
vector<int> A;

int dp[1 << 20];

int F (int mask) {
	if (mask + 1 == (1 << N)) return 0;
	if (~dp[mask]) return dp[mask];
    vector<pair<int,int>> v;
    for (int i = 0 ; i < N ; i++) if (!(mask & (1 << i))) v.emplace_back(A[i], i);
    int M = v.size();
    int ret = 10000;
    for (int j = 0 ; j < M ; j++) {
        for (int k = 0 ; k < M ; k++) {
            if (v[j].first == -v[k].first and v[j].first < 0) {
                int cost = j + k - (j < k);
                ret = min(ret, F(mask + (1 << v[j].second) + (1 << v[k].second)) + cost);
            }
        }
    }
    return dp[mask] = ret;
}


long long count_swaps(std::vector<int> s) {
	memset(dp, -1, sizeof dp);
	N = s.size();
	swap(s, A);
	return F(0);
	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