Submission #297336

#	Time	Username	Problem	Language	Result	Execution time	Memory
297336		Saboon	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	379 ms	27920 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
map<int,set<int>> S;

long long count_swaps(vector<int> a){
	vector<pair<int,int>> Joft;
	for (int i = 0; i < a.size(); i++){
		int x = a[i];
		if (!S[-x].empty()){
			Joft.push_back({*S[-x].begin(),i});
			S[-x].erase(S[-x].begin());
		}
		else
			S[x].insert(i);
	}
	sort(Joft.begin(), Joft.end(), [](pair<int,int> A, pair<int,int> B){
		return A.first+A.second < B.first+B.second;
	});
	long long ret = 0;
	int now = 0;
	for (int i = 0; i < a.size(); i+=2){
		int v = Joft[now].first, u = Joft[now].second;
		now ++;
		if (a[v] > a[u])
			ret += 2;
		ret += abs(i-v);
		ret += abs(i+1-u);
	}
	return ret/2;
}

Compilation message (stderr)

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

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