Submission #1292606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292606		ortsac	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	317 ms	407496 KiB

shoes

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

using namespace std;

#define int long long

const int MAXN = 2e5 + 10;

int bit[MAXN];

void add(int po) {
	po++;
	for (; po < MAXN; po += (po & -po)) bit[po]++;
}

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

int srange(int l, int r) {
	l++;
	r++;
	return (pf(r) - pf(l - 1));
}

int count_swaps(vector<int32_t> s) {
	int n = s.size();
	memset(bit, 0, sizeof bit);
	vector<bool> mark(n);
	vector<vector<queue<int>>> pos(2, vector<queue<int>>(n + 1));
	for (int i = 0; i < n; i++) pos[s[i] > 0][abs(s[i])].push(i);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (mark[i]) continue;
		int abv = (s[i] > 0);
		int nxt = pos[1 - abv][abs(s[i])].front();
		// i ... nxt
		int qtdRe = srange(i, nxt); // quantos já foram removidos
		int swaps = (nxt - i - 1 - qtdRe);
		if (abv == 1) swaps++; // se for positivo
		//cout << i << " " << nxt << " " << swaps << " " << qtdRe << "\n";
		ans += swaps;
		pos[0][abs(s[i])].pop();
		pos[1][abs(s[i])].pop();
		mark[i] = mark[nxt] = 1;
		add(i);
		add(nxt);
		//cout << pf(2) << "\n";
	}
	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