Submission #1303341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303341		aloo123	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1095 ms	16040 KiB

shoes

#include "shoes.h"
#include <set>
#include <map>
#include <climits>
#include <iostream>
#include <assert.h>

using namespace std;

long long count_swaps(std::vector<int> s) {
	int n = s.size() / 2;
	long long ans = 0;
	multiset<int> se;
	for(int &x: s) {
		if(x > 0) se.insert(x);
	}
	for(int i = 0;i<n*2;i+=2) {
		// get to 0
		map<int,int> posL, posR;
		for(int j = i;j<(int)s.size();j++) {
			if(s[j] < 0) {
				if(posL.count(s[j]) == 0) posL[s[j]] = j;
				else posL[s[j]] = min(posL[s[j]], j);
			}else {
				if(posR.count(s[j]) == 0) posR[s[j]] = j;
				else posR[s[j]] = min(posR[s[j]], j);
			}
		}
		int which = -1;
		int mn = INT_MAX;
		for(auto yo: posL) {
			int cst = (yo.second - i) + (posR[-yo.first] - i);
			if(yo.second < posR[-yo.first]) cst--;
			if(cst < mn) {
				which = yo.first;
				mn = cst;
			}
		}
		int L = posL[which];
		int R = posR[-which];
		if(posL[which] < posR[-which]) {
			s.erase(s.begin() + posL[which]);
			s.erase(s.begin() + posR[-which] - 1);
		}else {
			assert(posR[-which] < posL[which]);
			s.erase(s.begin() + posR[-which]);
			s.erase(s.begin() + posL[which] - 1);
		}
		s.insert(s.begin() + i, which);
		s.insert(s.begin() + i+1, -which);
		ans += mn;
		// cout << "which = " << which << endl;
		// for(int &x: s) cout << x << " ";
		// cout << endl;
	}
	return ans;
}


// . . . . . -1 -2 2 ...... 1
// pos[-1] + pos[1]
// min(pos[-L] + pos[+L])

//   h j k l -1 1 

// 5

// -x +x -> pos[-x] + pos[x] - 1
// +x -x -> pos[-x] + pos[x]


// // .... 1. -
// int main() {
// 	cout << count_swaps({-2, 2, 2, -2, -2, 2}) << endl;
// 	return 0;
// }

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