Submission #1243050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243050		nvujica	Arranging Shoes (IOI19_shoes)	C++20	65 / 100	32 ms	13896 KiB

shoes

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

using namespace std;

const int maxn = 1e5 + 10;

vector <int> l[maxn];
vector <int> r[maxn];
int loga[2 * maxn];
int par[2 * maxn];

void update(int x, int val){
	for(x; x < maxn; x += x & -x) loga[x] += val;
}

int query(int x){
	int ret = 0;

	for(x; x > 0; x -= x & -x) ret += loga[x];

	return ret;
}

long long count_swaps(vector<int> s) {
	int n = s.size() / 2;
	
	long long ans = 0;

	for(int i = 0; i < 2 * n; i++){
		int x = abs(s[i]);

		if(s[i] > 0) r[x].push_back(i + 1);
		else l[x].push_back(i + 1);
	}

	for(int i = 1; i <= n; i++){
		for(int j = 0; j < l[i].size(); j++){
			if(l[i][j] > r[i][j]){
				ans++;
				par[l[i][j]] = r[i][j];
				par[r[i][j]] = -1;
			}
			else {
				par[r[i][j]] = l[i][j];
				par[l[i][j]] = -1;
			}
		}
	}

	// cout << ans << endl;

	for(int i = 1; i <= 2 * n; i++){
		if(par[i] == -1) continue;

		int p = par[i];

		ans += query(p);
		update(1, 2);
		update(p, -1);
		update(i, -1);
	}

	return ans;
}

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