Submission #1241590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241590		The_Samurai	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	317 ms	146796 KiB

shoes

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

struct fenwick {
	vector<int> tree;
	int n;
	
	void init(int len) {
		n = len;
		tree.assign(n + 1, 0);
	}

	void upd(int i, int v) {
		for (i++; i <= n; i += i & (-i)) tree[i] += v;
	}

	int get(int i) {
		int sum = 0;
		for (i++; i > 0; i -= i & (-i)) sum += tree[i];
		return sum;
	}

	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};

long long count_swaps(std::vector<int> s) {
	map<int, queue<int>> mp;
	vector<int> vec;
	ll ans = 0;
	fenwick fw; fw.init(s.size());
	for (int i = 0; i < s.size(); i++) {
		if (!mp[-s[i]].empty()) {
			int j = mp[-s[i]].front(); mp[-s[i]].pop();
			ans += fw.get(j + 1, s.size() - 1);
			// cout << i << ' ' << j << ' ' << ans << endl;
			if (s[i] < 0) ans++;
			fw.upd(j, 1);
		} else {
			mp[s[i]].push(i);
			fw.upd(i, 1);
		}
	}
	// for (int x: vec) cout << x << ' ';
	// cout << endl;
	// for (int i = 1; i < vec.size(); i += 2) assert(vec[i] == -vec[i - 1]);
	// for (int i = 1; i < vec.size(); i += 2) assert(min(vec[i], vec[i - 1]) == vec[i - 1]);
	return ans;
}

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