Submission #210906

#	Time	Username	Problem	Language	Result	Execution time	Memory
210906		Kevin_Zhang_TW	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	126 ms	19836 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 200100;
using ll = long long;
int v[maxn], n;
bool used[maxn];
void add(int i, int d) {
	for (;i <= n;i += i & -i) v[i] += d;
}
int query(int i) {
	int res = 0;
	for (;i;i ^= i & -i) res += v[i];
	return res;
}
vector<int> pos[2][maxn];
long long count_swaps(std::vector<int> s) {
	ll res = 0;
	n = s.size();
	fill(used, used + n + 1, false);
	fill(v, v + n + 1, 0);
	for (int i = 0;i <= n;++i)
	   	pos[0][i].clear(), pos[1][i].clear();

	for (int i = n-1;i >= 0;--i) 
		pos[s[i] > 0][ abs(s[i]) ].pb(i);
	for (int i = 0;i < n;++i) if (!used[i]) {
		pos[s[i] > 0][ abs(s[i]) ].pop_back();
		vector<int> &v = pos[s[i] < 0][ abs(s[i]) ];

		res += (v.back()-i-1) - (query(v.back()-1) - query(i)) + (s[i] > 0);
		used[ v.back() ] = true;
		add( v.back(), 1);
	
		v.pop_back();
	}
	return res;
}
	

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