Submission #1036259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036259		happy_node	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	430 ms	35336 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=2e5+5;

struct fenwick {
	int t[MX];

	void upd(int v, int x) {
		v++;
		for(int i=v;i<MX;i+=i&-i) t[i]+=x;
	} 

	int que(int v) {
		v++;
		int res=0;
		for(int i=v;i>0;i-=i&-i) res+=t[i];
		return res;
	}
} ft;

map<int, vector<int>> pos;

long long count_swaps(vector<int> S) {
	int N=S.size()/2;

	ll ans=0;

	for(int i=0;i<2*N;i++) ft.upd(i,1);

	set<int> st;
	for(int i=2*N-1;i>=0;i--) {
		pos[S[i]].push_back(i);
		st.insert(i);
	}

	for(int i=1;i<2*N;i+=2) {
		int b=*st.begin();
		ft.upd(b,-1);
		st.erase(st.begin());
		pos[S[b]].pop_back();

		int j=pos[-S[b]].back();
		pos[-S[b]].pop_back();
		ft.upd(j,-1);
		st.erase(j);

		ans+=ft.que(j);

		if(S[b]>0) {
			ans++;
		}
	}

	return ans;
}

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