Submission #401758

#	Time	Username	Problem	Language	Result	Execution time	Memory
401758		nikatamliani	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	266 ms	274392 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
long long count_swaps(vector<int> A) {
	int n = (int)A.size();
	vector<queue<int>> positives(n+1);
	vector<queue<int>> negatives(n+1);
	vector<int> partner(n);
	for(int i = 0; i < n; ++i) {
		auto &positions = A[i] < 0 ? positives[-A[i]] : negatives[A[i]];
		if(positions.empty()) {
			if(A[i] > 0) {
				positives[A[i]].push(i);
			} else {
				negatives[-A[i]].push(i);
			}
		} else {
			partner[i] = positions.front();
			partner[positions.front()] = i;
			positions.pop();
 		}
	}
	vector<int> fenwick(n+1);
	auto sum = [&](int id) -> int {
		int answer = 0;
		for(++id; id > 0; id -= id & -id) {
			answer += fenwick[id];
		}
		return answer;
	};
	auto update = [&](int id, int v) {
		for(; id <= n; id += id & -id) {
			fenwick[id] += v;
		}
	};
	auto add = [&](int l, int r, int v) {
		++l, ++r;
		update(l, v);
		update(r+1, -v);
	};
	vector<bool> processed(n, false);
	long long answer = 0;
	for(int i = 0; i < n; ++i) {
		if(!processed[i]) {
			int j = partner[i];
			processed[i] = processed[j] = true;
			int real_i = sum(i) + i;
			int real_j = sum(j) + j;
			answer += real_j - real_i - (A[j] > 0);
			add(i, j, 1);
		}
	}
	return answer;
}

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