Submission #427163

#	Time	Username	Problem	Language	Result	Execution time	Memory
427163		dreezy	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1096 ms	140868 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pb push_back
#define pi pair<int,int>
long long count_swaps(vector<int> s) {
	
	ll ans = 1e18;
	int n = s.size();
	vector<pi> lefts(n/2);
	int cntleft = 0;
	vector<pair<int, pi>> sortlefts(n/2);
	
	vector<queue<int>> rightinds(n);
	for(int i =0; i<n ;i++){
		if(s[i] > 0){
			rightinds[s[i]].push(i);
		}
	}
	for(int i =0; i<n; i++){
		if(s[i] < 0){
			int firstright = rightinds[-s[i]].front();
			rightinds[-s[i]].pop();
			lefts[cntleft++] = {i, firstright};
			sortlefts[cntleft - 1] = {i+firstright, {i, firstright}};
		}
	}
	
	sort(sortlefts.begin(), sortlefts.end());
	
	for(int i =0; i<n/2; i++){
		lefts[i] = sortlefts[i].second;
	}
	
		
	ll posans = 0;
	vector<int> inds(n);
	for(int i =0; i<n ;i++) inds[i] = i;

	//for(int i =0; i<n/ 2; i++) cout << lefts[i]<<", "; cout <<endl;
	int l = 0;
	for(pi shoe : lefts){
		//get first availabe

		int leftind = shoe.first;
		int rightind = shoe.second;
		//cout <<endl;

		ll dist1 = abs(inds[leftind] - 2 * l);
		
		for(int k = 0; k<n ;k++){
			if(inds[k] >= 2 * l && inds[k] < inds[leftind])
			inds[k]++;
		}
		
		ll dist2 = abs(inds[rightind] -( 2 * l + 1));
		for(int k =0;k<n; k++){
			if(inds[k] >=2* l + 1 and inds[k] < inds[rightind])
				inds[k]++;
		}
		
		//cout << inds[lefts[l]]<<", "<<inds[firstright]<<": ";
		
		//cout << lefts[l]<<", "<<firstright<<": "<<dist1<<", "<<dist2<<endl;
		posans += dist1 + dist2;
		l++;
	}
	
	ans = min(ans, posans);
	
	//cout << posans<<endl<<endl;
		
	
	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