Submission #1261076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261076		Megalosaurus	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	222 ms	30160 KiB

shoes

#include "shoes.h"
// #include "grader.cpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>

using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

long long count_swaps(std::vector<int> s) {
	int n = s.size();
	map<int,set<int>>mp;
	for(int i = 0; i < n; i++)
	{
		mp[s[i]].insert(i);
	}
	ordered_set os;
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		if(os.find(i) != os.end()) continue;
		int sz = os.size();
		int idx = *mp[-s[i]].upper_bound(i);
		int a = sz-os.order_of_key(i), b = sz-os.order_of_key(idx);
		ans += idx-i-a+b-1;
		if(s[i] > 0) ans++;
		os.insert(idx);
		mp[-s[i]].erase(idx);
	}
	return ans;
}

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