Submission #725801

#	Time	Username	Problem	Language	Result	Execution time	Memory
725801		alvingogo	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	109 ms	138572 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;

long long count_swaps(vector<int> s) {
	int n=s.size();
	long long ans=0;
	vector<queue<pair<int,int> > > cnt(n+1);
	for(int i=0;i<n;i++){
		int u=abs(s[i]);
		if(!cnt[u].size() || cnt[u].front().fs==s[i]){
			cnt[u].push({s[i],i});
		}
		else{
			ans+=(i-cnt[u].front().sc-1);
			if(s[i]<0){
				ans+=2;
			}
			if(i==cnt[u].front().sc+1 && i%2==0){
				ans+=2;
			}
			cnt[u].pop();
		}
	}
	return ans/2;
}

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