Submission #1047400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047400		Kel_Mahmut	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	74 ms	23888 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

struct fenwick{
	int n;
	vector<int> fen;
	fenwick(int n) : n(n), fen(n){}

	void upd(int pos, int val){
		for(; pos < n; pos |= pos + 1)
			fen[pos] += val;
	}

	int index(int ind){
		int ret = 0;
		for(; ind >= 0; ind = (ind & (ind + 1)) - 1)
			ret += fen[ind];
		return ret;
	}
};

ll count_swaps(vector<int> v){
	int n = v.size() / 2;
	set<int> negative;
	set<int> positive;
	vector<vector<int>> posoccurence(n + 1), negoccurence(n + 1);

	for(int i = 2 * n - 1; i >= 0; i--){
		if(v[i] < 0) negative.insert(i);
		else posoccurence[v[i]].pb(i), positive.insert(i);
	}

	for(int i = 0; i < 2 * n; i++)
		if(v[i] < 0) negoccurence[-v[i]].pb(i);

	fenwick fen(2 * n);
	ll ans = 0;

	for(int i = 0; i < 2 * n; i++)
		fen.upd(i, 1);

	for(int i = 0; i < n; i++){
		if(fen.index(*negative.begin()) != 1 && fen.index(2 * n - 1) == fen.index(*prev(positive.end()))){
			int pos = *prev(positive.end());
			positive.erase(pos);
			int val = v[pos];
			fen.upd(pos, -1);
			pos = fen.index(pos);
			ans += fen.index(2 * n - 1) - pos;

			int neg = negoccurence[val].back(); negoccurence[val].pop_back();
			fen.upd(neg, -1);
			negative.erase(neg);
			neg = fen.index(neg);
			ans += fen.index(2 * n - 1) - neg;

		}
		else{
			int neg = *negative.begin(); negative.erase(negative.begin());
			int val = v[neg];
			fen.upd(neg, -1);
			neg = fen.index(neg);
			ans += neg;

			int pos = posoccurence[-val].back();
			posoccurence[-val].pop_back();
			fen.upd(pos, -1);
			positive.erase(pos);
			pos = fen.index(pos);
			ans += pos;
		}
	}
	return ans;
}

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