Submission #1047261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047261		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	192 ms	24660 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct BIT {
	int n;
	vector<int> e;
	BIT(int b) {
		b++;
		e.resize(b);
		n=b;
	}
	void upd(int at, int val) {
		at++;
		while(at<n) {
			e[at]+=val;
			at+=at&(-at);
		}
	}
	int que(int at) {
		int sum=0;
		at++;
		while(at >0) {
			sum+=e[at];
			at-=at&(-at);
		}
		return sum;
	}
};
long long count_swaps(std::vector<int> s) {
	int n= s.size();
	int ans=0;
	BIT b(n);
	for(int i = 0;i<n;i++)b.upd(i, 1);
	map<int, vector<int>> mp;
	for(int i = n-1;i>=0;i--) {
		mp[s[i]].push_back(i);
	}
	for(int i = 0;i<n;i++) {
		if(s[i] == 0)continue;
		int at = mp[-s[i]].back();
//		cout << i << " " << b.que(i) << " " << b.que(at) << " " << s[i] << endl;
		ans+=b.que(at)-b.que(i)-1;
		b.upd(at, -1);
		b.upd(i, -1);
		mp[-s[i]].pop_back();
		mp[s[i]].pop_back();
		if(s[i] > 0)ans++;
		s[i]=0;
		s[at]=0;
	}
	return ans;
}

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