제출 #465908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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;
}

컴파일 시 표준 에러 (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