Submission #1151577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151577		Pacybwoah	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1095 ms	4520 KiB

shoes

#include "shoes.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
namespace{
	struct BIT{
		vector<int> bit;
		int n;
		BIT(int _n){
			n = _n;
			bit.resize(n + 1);
		}
		void modify(int pos, int val){
			while(pos <= n){
				bit[pos] += val;
				pos += (pos & -pos);
			}
		}
		int query(int pos){
			int ans = 0;
			while(pos > 0){
				ans += bit[pos];
				pos -= (pos & -pos);
			}
			return ans;
		}
	};
}

long long count_swaps(std::vector<int> s) {
	ll ans = 0;
	int n = (int)s.size() / 2;
	vector<pair<int, int>> cp;
	for(int i = 0; i < 2 * n; i++){
		if(s[i] > 0) cp.emplace_back(s[i], i);
	}
	sort(cp.begin(), cp.end());
	for(int i = 0; i < n; i++){
		s[cp[i].second] = i + 1;
	}
	vector<pair<int, int>>().swap(cp);
	for(int i = 0; i < 2 * n; i++){
		if(s[i] < 0) cp.emplace_back(-s[i], i);
	}
	sort(cp.begin(), cp.end());
	for(int i = 0; i < n; i++){
		s[cp[i].second] = -(i + 1);
	}
	BIT bit(2 * n);
	for(int i = 1; i <= 2 * n; i++) bit.modify(i, 1);
	vector<pair<int, int>> pos(n + 1);
	for(int i = 0; i < 2 * n; i++){
		if(s[i] < 0) pos[-s[i]].first = i + 1;
		else pos[s[i]].second = i + 1;
	}
	sort(next(pos.begin()), pos.end());
	for(int i = n; i > 0; i--){
		int best = 1;
		for(int j = 1; j <= i; j++){
			if(bit.query(pos[j].first) + bit.query(pos[j].second) < bit.query(pos[best].first) + bit.query(pos[best].second)) best = j;
		}
		ans += bit.query(pos[best].first) + bit.query(pos[best].second) - 3;
		if(pos[best].first > pos[best].second) ans++;
		bit.modify(pos[best].first, -1);
		bit.modify(pos[best].second, -1);
		pos.erase(pos.begin() + best);
	}
	return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run shoes.cpp grader.cpp

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