Submission #442539

#	Time	Username	Problem	Language	Result	Execution time	Memory
442539		zxcvbnm	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1083 ms	21428 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
/*
4
1 2 3 -4 4 -2 -1 -3

4
1 2 3 -4 -2 4 -1 -3

5
3 2 2 -2 3 2 -3 -2 -2 -3

4
1 2 3 4 -4 -3 -2 -1

5
1 2 3 4 4 -1 -2 -3 -4 -4

*/
int n;
map<vector<int>, int> used;
int mn = 30;
bool ok(vector<int> a) {
	for(int i = 0; i < n; i+=2) {
		if (a[i] == -a[i+1] && a[i] < 0) continue;
		return false;
	}
	return true;
}
void go(vector<int> a, int swaps, vector<vector<int>> path, map<int, int> add) {
	if (used.count(a) && used[a] <= swaps) return;
	if (swaps >= mn) return;
	used[a] = swaps;

	if (ok(a)) {
//		cout << swaps << "\n";
		if (swaps < mn) {
			mn = swaps;
			cerr << mn << "\n";
			for(auto i : path) {
				for(int j : i) {
					cout << j << " ";
				}
				cout << "\n";
			}
			cerr << "\n";
		}
		for(auto i : add) {
			cout << i.first << " " << i.second << "\n";
		}
		return;
	}

	for(int i = 0; i < n; i++) {
		vector<int> b = a;
		if (i != 0) {
			add[b[i]]++;
			add[b[i-1]]++;
			swap(b[i-1], b[i]);
			path.push_back(b);
			go(b, swaps+1, path, add);
			path.pop_back();
			add[b[i]]--;
			add[b[i-1]]--;
			swap(b[i-1], b[i]);
		}
		if (i != n-1) {
			add[b[i]]++;
			add[b[i+1]]++;
			swap(b[i], b[i+1]);
			path.push_back(b);
			go(b, swaps+1, path, add);
			add[b[i]]--;
			add[b[i+1]]--;
			path.pop_back();
			swap(b[i], b[i+1]);
		}
	}
}
long long count_swaps(std::vector<int> s) {
	n = s.size();
	vector<int> a = s;

	int sum = 0, open = 0, closed = 0;
	for(int i = 0; i < n; i++) {
		map<int, int> cnt;
		bool found = false;
		for(int j = i+1; j < n; j++) {
			if (a[j] == -a[i]) {
				if (a[j] < 0) sum++;
				found = true;
				break;
			}
			cnt[a[j]]++;
		}
		if (!found) continue;
		for(int j = 1; j <= n; j++) {
			closed += min(cnt[j], cnt[-j]);
			open += abs(cnt[j] - cnt[-j]);
		}
	}
//	cout << open << " " << closed << " " << sum << "\n";
	sum += ceil((double) open / 2) + 2 * closed;

	vector<vector<int>> temp1;
	map<int, int> temp2;
//	go(a, 0, temp1, temp2);

//	cout << mn << "\n";
	return sum;
}

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