Submission #1010905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010905		alex_2008	Arranging Shoes (IOI19_shoes)	C++14	30 / 100	1097 ms	4564 KiB

shoes

#include "shoes.h"
//#include "fish.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1000 + 10, M = 110;
bool used[N];
ll count_swaps(vector<int> S) {
	int n = (int)S.size() / 2;
	vector <int> v;
	for (auto &it : S) {
		if (it > 0) v.push_back(it);
	}
	sort(v.begin(), v.end());
	int ans = 0;
	vector <int> s = S;
	for (int j = 0; j < (int)v.size(); j++) {
		for (int i = 2 * j; i < 2 * n; i++) {
			if (v[j] == -s[i]) {
				for (int k = i; k > 2 * j; k--) {
					swap(s[k], s[k - 1]);
				}
				ans += abs(i - 2 * j);
				break;
			}
		}
		for (int i = 2 * j + 1; i < 2 * n; i++) {
			if (v[j] == s[i]) {
				for (int k = i; k > 2 * j + 1; k--) {
					swap(s[k], s[k - 1]);
				}
				ans += abs(i - 2 * j - 1);
				break;
			}
		}
	}
	//cout << ans << "\n";
	while (next_permutation(v.begin(), v.end())) {
		int cur_ans = 0;
		vector <int> s = S;
		for (int j = 0; j < (int)v.size(); j++) {
			for (int i = 2 * j; i < 2 * n; i++) {
				if (v[j] == -s[i]) {
					for (int k = i; k > 2 * j; k--) {
						swap(s[k], s[k - 1]);
					}
					cur_ans += abs(i - 2 * j);
					break;
				}
			}
			for (int i = 2 * j + 1; i < 2 * n; i++) {
				if (v[j] == s[i]) {
					for (int k = i; k > 2 * j + 1; k--) {
						swap(s[k], s[k - 1]);
					}
					cur_ans += abs(i - 2 * j - 1);
					break;
				}
			}
		}
		ans = min(ans, cur_ans);
	}
	//cout << ans << "\n";
	return ans;
}
/*
int main() {
	//cout << count_swaps({ -2, 2, 2, -2, -2, 2 }) << "\n";
}
*/

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