Submission #152034

#	Time	Username	Problem	Language	Result	Execution time	Memory
152034		oolimry	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1076 ms	3896 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> s) {
	int n = s.size() / 2;
	
	int minv[2*n];
	int ans = 0;
	for(int pos = 0;pos < n;pos++){
		fill(minv,minv+2*n,2*n);
		for(int i = 2*pos;i < 2*n;i++){
			if(s[i] < 0){
				minv[s[i]*-1 - 1] = min(minv[s[i]*-1 - 1],i);
			}
			else{
				minv[s[i] - 1 + n] = min(minv[s[i] - 1 + n],i);
			}
		}
		
		int minno = 0;
		int mincost = 134344323;
		for(int i = 0;i < n;i++){
			//cout << minv[i] << " " << minv[n+i] << "\n";
			int l = minv[i];
			int r = minv[n+i];
			int cost = 0;
			cost += (l - 2*pos);
			cost += (r - (2*pos+1));
			if(l > r) cost++;
			if(cost < mincost){
				mincost = cost;
				minno = i;
			}
		}
		//cout << minno << "\n";
		int l = minv[minno];
		int r = minv[minno + n];
		
		if(l < r){
			while(l > 2 * pos){
				ans++;
				swap(s[l],s[l-1]);
				l--;
			}
			while(r > 2 * pos + 1){
				ans++;
				swap(s[r],s[r-1]);
				r--;
			}
		}
		else{
			while(r > 2 * pos){
				ans++;
				swap(s[r],s[r-1]);
				r--;
			}
			while(l > 2 * pos + 1){
				ans++;
				swap(s[l],s[l-1]);
				l--;
			}
			swap(s[2*pos],s[2*pos+1]);
			ans++;
		}
		
		for(int i = 0;i < 2 * n;i++){
			//cout << s[i] << " ";
		}
		//cout << "\n";
	}
	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