Submission #285721

#	Time	Username	Problem	Language	Result	Execution time	Memory
285721		williamMBDK	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	289 ms	29548 KiB

shoes

#include<bits/stdc++.h>
#define int long long
#include "shoes.h"
using namespace std;
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) {
	int N = s.size();
	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 count_swaps(vector<signed> s){
	int N = s.size();
	vector<int> indices;
	for(int i = 0; i < N; i++){
		if(s[i] < 0) indices.push_back(i);
	}
	vector<int> temp (N / 2);
	for(int i = 0; i < N / 2; i++) temp[i] = i; 
	return count_swaps_perm(s, indices, temp);
}

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