Submission #784153

#	Time	Username	Problem	Language	Result	Execution time	Memory
784153		Alfraganus	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	111 ms	16120 KiB

shoes

#include "shoes.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;

struct SegTree {

	int size = 1;
	vector<int> mins;

	SegTree(int n){
		while(size < n)size *= 2;
		mins.resize(2 * size);
	}

	void set(int i, int x, int lx, int rx){
		if(rx - lx == 1){
			mins[x] = 1;
			return;
		}
		int m = (lx + rx) >> 1;
		if(i < m)set(i, 2 * x + 1, lx, m);
		else set(i, 2 * x + 2, m, rx);
		mins[x] = mins[2 * x + 1] + mins[2 * x + 2];
	}

	void set(int i){
		set(i, 0, 0, size);
	}

	int sum(int l, int r, int x, int lx, int rx){
		if(l <= lx and rx <= r)return mins[x];
		if(r <= lx or rx <= l)return 0;
		int m = (lx + rx) >> 1;
		return sum(l, r, 2 * x + 1, lx, m) + sum(l, r, 2 * x + 2, m, rx);
	}

	int sum(int l, int r){
		return sum(l, r, 0, 0, size);
	}

	void printtree(){
		for(auto x : mins)cout<< x << ' ';
		cout<<endl;
	}
};

long long count_swaps(vector<int> a) {
	long long n = a.size() / 2;
	if(n == 1)return a[0] > 0;
	vector<vector<int>> pos(2 * n + 1);
	for(int i = 2 * n - 1; i >= 0; i --)
		pos[a[i] + n].push_back(i);
	long long ans = 0;
	SegTree s(2 * n);
	for(int i = 0; i < 2 * n; i ++){
		if(a[i] != 0){
			ans += pos[-a[i] + n].back() - i - s.sum(i, pos[-a[i] + n].back());
			if(a[i] < 0)ans --;
			s.set(pos[-a[i] + n].back());
			s.set(i);
			a[pos[-a[i] + n].back()] = 0;
			pos[-a[i] + n].pop_back();
			pos[a[i] + n].pop_back();
			a[i] = 0;
		}
	}
	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