Submission #683990

#	Time	Username	Problem	Language	Result	Execution time	Memory
683990		Juan	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	1 ms	2644 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
#define pii pair<int, int>
#define ff first
#define ss second

int64_t count_swaps(vector<int> S){
	int n = S.size();
	pii mp[maxn];
	int pref[maxn];
	for(int i = 0; i < n; i++){
		int val = abs(S[i]);
		if(mp[val].ff) mp[val].ss = i, pref[i] = pref[i-(i>0)]-1;
		else mp[val].ff = i, pref[i] = pref[i-(i>0)]+1;
	}

	int64_t ans = 0;
	for(int i = 0; i < n; i++){
		int val = abs(S[i]);
		int mn = min(mp[val].ff, mp[val].ss);
		int mx = max(mp[val].ff, mp[val].ss);
		if(i==mn){
			ans+= mx-mn-1 + (S[i]<0) - pref[mx];
		}
	}

	return ans;
}

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