Submission #143793

#	Time	Username	Problem	Language	Result	Execution time	Memory
143793		ainta	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	101 ms	14572 KiB

shoes

#include "shoes.h"
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define pii pair<int,int>

vector<int>A[101000], B[101000];
int n, BIT[201000];


void Add(int a, int b) {
	while (a <= 2 * n) {
		BIT[a] += b;
		a += (a&-a);
	}
}
int Sum(int a){
	int r = 0;
	while (a) {
		r += BIT[a];
		a -= (a&-a);
	}
	return r;
}

vector<pii>V;

long long count_swaps(std::vector<int> s) {
	int i, j;
	n = s.size() / 2;
	for (i = 0; i < 2 * n; i++) {
		if (s[i] < 0)A[-s[i]].push_back(i+1);
		else B[s[i]].push_back(i + 1);
	}
	long long res = 0;
	for (i = 1; i <= n; i++) {
		for (j = 0; j < A[i].size(); j++) {
			int t1 = A[i][j], t2 = B[i][j];
			if (t1 > t2) {
				res++;
				swap(t1, t2);
			}
			V.push_back({ t1,t2 });
		}
	}
	sort(V.begin(), V.end());
	for (auto &t : V) {
		int s1 = Sum(t.first);
		int s2 = Sum(t.second);
		int s3 = Sum(2 * n);
		res += s2 - s1 + (s3 - s2) * 2;
		Add(t.second, 1);
	}
	return res;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < A[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