Submission #285745

#	Time	Username	Problem	Language	Result	Execution time	Memory
285745		williamMBDK	Arranging Shoes (IOI19_shoes)	C++14	65 / 100	296 ms	29036 KiB

shoes

#include<bits/stdc++.h>
#define int long long
#include "shoes.h"
using namespace std;
int N;
struct BIT{
	int N;
	vector<int> arr;
	BIT(int N){
		this->N = N;
		arr = vector<int> (N);
	}
	int q(int idx){
		int s = 0;
		while(idx > 0){
			s += arr[idx];
			idx -= (idx & (-idx));
		}
		return s;
	}
	void u(int idx, int val){
		while(idx < N){
			arr[idx] += val;
			idx += (idx & (-idx));
		}
	}
	
};
int count_swaps_perm(vector<signed>& s, vector<int>& indices, vector<int>& perm) {
	BIT bit (N + 1);
	map<int,pair<int,vector<int>>> mp;
	for(int i = 0; i < N; i++){
		mp[s[i]].second.push_back(i);
		bit.u(i + 1, i);
		if(i < N - 1) bit.u(i + 2, -i);
	}
	int res = 0;
	for(int i = 0; i < N / 2; i++){
		int idx1 = indices[perm[i]];
		res += bit.q(idx1 + 1);
		if(idx1 < N - 1) bit.u(idx1 + 2, -1);
		int idx2 = mp[s[idx1] * -1].second[mp[s[idx1] * -1].first++];
		res += bit.q(idx2 + 1);
		if(idx2 < N - 1) bit.u(idx2 + 2,-1);
	}
	return res;
}

int rec(vector<signed>& s, vector<int>& indices, vector<int>& perm, vector<bool>& used, int idx){
	if(idx == N / 2){
		return count_swaps_perm(s, indices, perm);
	}
	int res = LLONG_MAX;
	for(int i = 0; i < N / 2; i++){
		if(used[i]) continue;
		perm[idx] = i;
		used[i] = 1;
		res = min(res, rec(s, indices, perm, used, idx + 1));
		used[i] = 0;
		perm[idx] = -1;
	}
	return res;
}

int count_swaps_brute(vector<signed> s, vector<int> indices){
	vector<bool> used (N / 2);
	vector<int> perm (N / 2);
	return rec(s, indices, perm, used, 0); 
}
int count_swaps_fast(vector<signed> s, vector<int> indices){
	vector<int> temp (N / 2);
	for(int i = 0; i < N / 2; i++) temp[i] = i; 
	return count_swaps_perm(s, indices, temp);
}
int count_swaps(vector<signed> s){
	N = s.size();
	vector<int> indices;
	for(int i = 0; i < N; i++){
		if(s[i] < 0) indices.push_back(i);
	}
	if(N <= 16) return count_swaps_brute(s, indices);
	else return count_swaps_fast(s, indices);
}

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