Submission #415259

#	Time	Username	Problem	Language	Result	Execution time	Memory
415259		peuch	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	100 ms	16784 KiB

shoes

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

bool cmp(pair<int, int> a, pair<int, int> b){
	return a.first + a.second < b.first + b.second;
}

long long count_swaps(std::vector<int> s) {
	int n = s.size() / 2;
	vector<vector<int> > colors[2] = {vector<vector<int> >(n + 1), vector<vector<int> >(n + 1)};
	vector<int> ids(2 * n);
	
	vector<int> bit(2 * n + 1);
	
	for(int i = 0; i < 2 * n; i++)
		colors[(s[i] < 0) ? 0 : 1][abs(s[i])].push_back(i);
	
	vector<pair<int, int> > ord;
	
	for(int i = 0; i < colors[0].size(); i++)
		for(int j = 0; j < colors[0][i].size(); j++)
			ord.push_back(make_pair(colors[0][i][j], colors[1][i][j]));
	sort(ord.begin(), ord.end(), cmp);
	
	for(int i = 0; i < ord.size(); i++){
		ids[ord[i].first] = 2 * i;
		ids[ord[i].second] = 2 * i + 1;
	}
	
	long long ans = 0;
	
	for(int i = 2 * n - 1; i >= 0; i--){
		int id = ids[i] + 1;
		while(id > 0){
			ans += bit[id];
			id -= -id&id;
		}
		id = ids[i] + 1;
		while(id < 2 * n + 1){
			bit[id]++;
			id += -id&id;
		}
	}
	
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0; i < colors[0].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~~
shoes.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int j = 0; j < colors[0][i].size(); j++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~
shoes.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0; i < ord.size(); 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