Submission #465908

#	Time	Username	Problem	Language	Result	Execution time	Memory
465908		dattranxxx	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	79 ms	10296 KiB

shoes

/*
 * Author :  shora
 */
#include "shoes.h"
#include <bits/stdc++.h>
#define print(_v) for (auto &_ : _v) {cerr << _ << ' ';} cerr << endl;
using namespace std;
using ll = long long;
const int oo = 1e9;

struct BIT {
	int n; vector<int> bit;
	BIT(int n): n(n) {
		bit.resize(n + 1);
	}
	void update(int i, int x) {
		for (; i <= n; i += i & -i) 
			bit[i] += x;
	}
	int get(int i) {
		int res = 0;
		for (; i; i -= i & -i)
			res += bit[i];
		return res;
	}
};

long long count_swaps(std::vector<int> a) {
	int n = a.size() / 2;
	vector<vector<pair<int, int>>> idx(n + 1);
	for (int i = 0; i < a.size(); ++i) 
		idx[abs(a[i])].emplace_back(a[i], i);
	for (int i = 1; i <= n; ++i)
		sort(idx[i].begin(), idx[i].end());
	ll res = 0;
	vector<pair<int, int>> v;
	for (auto& p : idx) {
		for (int i = 0; i < p.size() / 2; ++i) {
			int l = p[i].second, r = p[i + p.size() / 2].second;
			if (l > r) swap(l, r), res++;
			v.emplace_back(l+1, r+1);
		}
	}
	BIT bit(n*2);
	for (int i = 1; i <= n*2; ++i) bit.update(i, 1);
	sort(v.begin(), v.end());
	for (auto& p : v) {
		res += bit.get(p.second-1) - bit.get(p.first);
		bit.update(p.first, -1);
		bit.update(p.second, -1);
	}
	return res;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i = 0; i < a.size(); ++i)
      |                  ~~^~~~~~~~~~
shoes.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int i = 0; i < p.size() / 2; ++i) {
      |                   ~~^~~~~~~~~~~~~~

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