Submission #285705

#	Time	Username	Problem	Language	Result	Execution time	Memory
285705		williamMBDK	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	324 ms	25464 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(vector<signed> s) {
	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; i++){
		if(s[i] < 0){
			res += bit.q(i + 1);
			if(i < N - 1) bit.u(i + 2, -1);
			
			int idx = mp[s[i] * -1].second[mp[s[i] * -1].first++];
			res += bit.q(idx + 1);
			if(idx < N - 1) bit.u(idx + 2,-1);
		}
	}
	return res;
}

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