Submission #427190

#	Time	Username	Problem	Language	Result	Execution time	Memory
427190		dreezy	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1087 ms	149720 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);
	set<int> shoes;
	for(int i =0; i<n ;i++){
		shoes.insert({i, 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;

		int newleftind = 2 * l;
		int cnt = 0;
		for(int ss : shoes){
			if(ss == leftind){
				
				newleftind += cnt;
			}
			cnt++;
		}
		
		ll dist1 = abs(newleftind - 2 * l);
		
		
		shoes.erase(shoes.find(leftind));
		
		int newrightind = 2 * l + 1;
		
		cnt = 0;
		for(int ss : shoes){
			if(ss == rightind){
				
				newrightind += cnt;
			}
			cnt++;
		}
		//cout <<leftind<<", "<<rightind<<": "<< newleftind<<", "<<newrightind<<endl;
		
		ll dist2 = abs(newrightind -( 2 * l + 1));
		shoes.erase(shoes.find(rightind));
		/*for(int ss : shoes){
			cout <<ss<<", ";
		}
		cout <<endl;
		*/
		//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