Submission #143575

#	Time	Username	Problem	Language	Result	Execution time	Memory
143575		abeker	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	99 ms	19192 KiB

shoes

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

typedef long long ll;

const int MAXN = 2e5 + 5;

int N;
vector <int> lft[MAXN], rig[MAXN];
int fen[MAXN];

void update(int x) {
	for (x++; x < MAXN; x += x & -x)
		fen[x]++;
}

int get(int x) {
	int res = 0;
	for (x++; x; x -= x & -x)
		res += fen[x];
	return res;
}
	
ll count_swaps(vector <int> shoes) {
	N = shoes.size();
	vector <int> todo(N, -1);
	for (int i = 0; i < N; i++) {
		int sz = abs(shoes[i]);
		if (shoes[i] < 0) 			
			lft[sz].push_back(i);
		else 
			rig[sz].push_back(i);
	}
	
	ll sol = 0;
	for (int i = 1; i <= N / 2; i++) 
		for (int j = 0; j < lft[i].size(); j++) {
			if (lft[i][j] > rig[i][j]) {
				swap(lft[i][j], rig[i][j]);
				sol++;
			}
			todo[rig[i][j]] = lft[i][j];
		}
	
	for (int i = 0; i < N; i++) 
		if (todo[i] != -1) {
			sol += get(N) - get(todo[i]);
			update(todo[i]);
			update(i);
		}
	
	return sol;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < lft[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~

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