Submission #1010967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010967		alex_2008	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	146 ms	4956 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 = 1e5 + 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 <= 1000) {
		ll ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 2 * n; j++) {
				//cout << S[j] << " ";
			}
			//cout << "\n";
			map <int, int> mp;
			for (int j = 2 * i; j < 2 * n; j++) {
				if (mp.find(S[j]) == mp.end()) {
					mp[S[j]] = j;
				}
			}
			pair <int, int> esim = make_pair(-1, -1);
			int cur = 2 * n + 10;
			for (auto it : mp) {
				//cout << "? " << it.first << "\n";
				if (it.first > 0) break;
				int x = it.second;
				int y = mp[-it.first];
				int f = 0;
				if (x < y) {
					f = x + y - 4 * i - 1;
				}
				else {
					f = x + y - 4 * i;
				}
				if (f < cur) {
					cur = f;
					esim = make_pair(x, y);
				}
			}
			//cout << esim.first << " " << esim.second << "\n";
			//cout << "#" << cur << "\n";
			for (int j = esim.first; j > 2 * i; j--) {
				swap(S[j], S[j - 1]);
			}
			for (int j = esim.second + (esim.first > esim.second); j > 2 * i + 1; j--) {
				swap(S[j], S[j - 1]);
			}
			ans += cur;
		}
		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, 1, -1, -2 }) << "\n";
}
*/

Compilation message (stderr)

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

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