Submission #376337

#	Time	Username	Problem	Language	Result	Execution time	Memory
376337		InternetPerson10	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	104 ms	16364 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <cmath>
typedef long long ll;

using namespace std;

struct FTree {
	vector<ll> nums;
	int size=1;
	void init(int n) {
		while(size < n) size *= 2;
		nums.resize(size+1);
	}
	void set(int n) {
		while(n <= size) {
			nums[n]++;
			n += (n & -(n));
		}
	}
	ll get(int n) {
		ll ans = 0;
		while(n > 0) {
			ans += nums[n];
			n -= (n & -(n));
		}
		return ans;
	}
	void print() {
		for(int i = 0; i <= size; i++) cout << nums[i] << ' ';
		cout << '\n';
	}
};

vector<vector<int>> ct;
bool taken[200002];

ll count_swaps(vector<int> s) {
	int n = s.size();
	n /= 2;
	ll ans = 0;
	ct.resize(2*n+1);
	for(int i = 2*n-1; i >= 0; i--) {
		ct[n+s[i]].push_back(i+1);
	}
	FTree ft;
	ft.init(2*n);
	for(int i = 0; i < 2*n; i++) {
		if(taken[i]) continue;
		int x = s[i];
		int a = ct[n+x].back(), b = ct[n-x].back();
		ct[n+x].pop_back(); ct[n-x].pop_back();
		if(x < 0) ans--;
		int bb = ft.get(b), aa = ft.get(a);
		ans += std::abs(b-a) - std::abs(bb - aa);
		ft.set(b);
		ft.set(a);
		taken[a-1] = taken[b-1] = true;
	}
	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