Submission #1016281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016281		igofan	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	74 ms	71784 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

struct Fen { //0 based index
	int n;
	vector<int> bit;
	Fen(int _n) : n(_n) {
		bit = vector<int>(n+1);
	}
	void add(int i, int val) {
		for(++i; i<=n; i+=i&-i) bit[i]+=val;
	}
	int sum(int i) { //[0, i]
		int ans = 0;
		for(++i; i>0; i-=i&-i) ans += bit[i];
		return ans;
	}
};

long long count_swaps(std::vector<int> s) {
	int n = s.size()/2;
	Fen fen(2*n+1);
	vector<queue<int>> v(n+1);
	long long ans = 0;
	for(int i=1; i<=2*n; i++) {
		int x = s[i-1];
		int a = abs(x);
		int sign = x / a;
		if (v[a].empty()) {
			v[a].push(i*sign); //i for right, -i for left
			fen.add(i, 1);
		} else {
			int j = v[a].front();
			if ((j<0 && x<0) || (j>0 && x>0)) {
				v[a].push(i*sign);
				fen.add(i, 1);
			} else {
				ans += (fen.sum(i) - fen.sum(abs(j)));
				if (j>0) ans++;
				fen.add(abs(j), 1);
				v[a].pop();
			}
		}
	}
	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