Submission #1181384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181384		peteza	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	44 ms	13896 KiB

shoes

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

vector<int> poses[100005][2];
int fwk[200005];
bool vis[200005];

void upd(int idx, int val) {
	//cout << idx << ' ';
	for(;idx <= 200000; idx+=idx&-idx)
		fwk[idx] += val;
}

int qr(int idx) {
	int sum = 0;
	for(;idx;idx-=idx&-idx)
		sum += fwk[idx];
	return sum;
}

int gcidx(int idx) {
	return idx - qr(idx);
}

long long count_swaps(std::vector<int> s) {
	long long res = 0;
	for(int i=s.size()-1;i>=0;i--) {
		if(s[i] < 0) poses[-s[i]][0].push_back(i);
		else poses[s[i]][1].push_back(i);
	}
	for(int i=0;i<s.size();i++) {
		if(vis[i]) continue;
		int bruhbruh = max(s[i], -s[i]);
		if(s[i] < 0) {
			int cl = gcidx(i+1), cr = gcidx(poses[-s[i]][1].back() + 1);
			res += (cr - cl - 1);
			upd(i+1, 1); upd(poses[-s[i]][1].back() + 1, 1);
		} else {
			int cl = gcidx(i+1), cr = gcidx(poses[s[i]][0].back() + 1);
			res += (cr - cl);
			upd(i+1, 1); upd(poses[s[i]][0].back() + 1, 1);
		}
		vis[poses[bruhbruh][0].back()] = 1;
		vis[poses[bruhbruh][1].back()] = 1;	
		poses[bruhbruh][0].pop_back();
		poses[bruhbruh][1].pop_back();
	}
	return res;
}

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