Submission #297392

#	Time	Username	Problem	Language	Result	Execution time	Memory
297392		Saboon	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	382 ms	28488 KiB

shoes

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

const int maxn = 1e6 + 10;
int fen[maxn];

void add(int idx){
	for (idx++; idx < maxn; idx += idx & -idx)
		fen[idx] ++;
}

int get(int idx){
	int ret = 0;
	for (idx++; idx; idx -= idx & -idx)
		ret += fen[idx];
	return ret;
}

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());
	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 ++;
		ret += v+u-1-get(v)-get(u) + (a[v] > a[u]);
		add(v), add(u);
	}
	return ret;
}

Compilation message (stderr)

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

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