Submission #1291711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291711		goulthen	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	142 ms	138244 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

#define ll long long
#define rep(i,a,b) for(int i = a; i <= b; i++)

int bit[200010],n;

int query(int i) {
	int ans = 0;
	for(;i>0; i-=(-i&i)) ans += bit[i];
	return ans;
}

void update(int i, int x) {
	if(i==0) return;
	for (; i<=n; i+=(-i&i)) bit[i] += x;
}

ll count_swaps(vector<int> s) {
	n = s.size();
	vector<deque<int>> pos(s.size()+1);
	vector<bool> mk(s.size());
	rep(i,0,n-1) {
		update(i+1,1);
		pos[s[i]+n/2].push_back(i);
	}
	ll ans = 0;
	rep(i,0,n-1) {
		if(mk[i]) continue;
		int j = pos[-s[i]+n/2].front();
		ans += query(j+1)-1;
		if(s[i] < 0) ans--;
		mk[j] = 1;
		update(i+1,-1);
		update(j+1,-1);
		pos[-s[i]+n/2].pop_front();
		pos[s[i]+n/2].pop_front();
	}
	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