Submission #1010914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010914		alex_2008	Arranging Shoes (IOI19_shoes)	C++14	65 / 100	27 ms	5076 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 = 2e5 + 10, M = 110;
bool used[N];
int fenwick[N];
void update(int ind, int diff, int n) {
	while (ind <= n) {
		fenwick[ind] += diff;
		ind += (ind & (-ind));
	}
}
int sm(int ind) {
	int ans = 0;
	while (ind > 0) {
		ans += fenwick[ind];
		ind -= (ind & (-ind));
	}
	return ans;
}
ll count_swaps(vector<int> S) {
	int n = (int)S.size() / 2;
	if (n <= 8) {
		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;
				}
			}
		}
		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);
		}
		return ans;
	}
	bool ch = true;
	for (auto& it : S) {
		if (abs(it) != abs(S[0])) ch = false;
	}
	if (ch) {
		//cout << "?\n";
		vector <int> a;
		vector <int> b;
		for (int i = 0; i < 2 * n; i++) {
			if (S[i] < 0) a.push_back(i + 1);
			else b.push_back(i + 1);
			update(i + 1, 1, 2 * n);
		}
		ll ans = 0;
		for (int i = 0; i < n; i++) {
			ans += sm(a[i] - 1); update(a[i], -1, 2 * n);
			ans += sm(b[i] - 1); update(b[i], -1, 2 * n);
		}
		return ans;
	}
}
/*
int main() {
	cout << count_swaps({ -2, 2, 2, -2, -2, 2 }) << "\n";
}
*/

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:106:1: warning: control reaches end of non-void function [-Wreturn-type]
  106 | }
      | ^

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