Submission #1056717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056717		jamesbamber	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	204 ms	77592 KiB

shoes

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

long long count_swaps(std::vector<int> s) {
	int n = s.size()/2;

	vector<int> numid(2*n);
	map<int, queue<int>> nums;
	int ct = 0;
	for(int i=0; i<2*n; i++){
		if(nums.count(s[i]) and nums[s[i]].size() != 0){
			numid[i] = nums[s[i]].front();
			nums[s[i]].pop();
		}
		else{
			numid[i] = ct;
			nums[-s[i]].push(ct);
			ct++;
		}
	}
	vector<int> perm(2*n);

	for(int i=0; i<2*n; i++){
		perm[i] = (s[i] > 0)?2*numid[i]+1:2*numid[i];
	}

	vector<int> fw(2*n+1);
	auto add = [&](int i, int x){
		for(; i<fw.size(); i+= i&-i) fw[i] += x;
	};
	auto query = [&](int i){
		int ans = 0;
		for(; i>0; i -= i&-i) ans += fw[i];
		return ans;
	};

	long long ans = 0;
	for(int i=0; i<2*n; i++){
		ans += i - query(perm[i]);
		add(perm[i]+1, 1);
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In lambda function:
shoes.cpp:30:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(; i<fw.size(); i+= i&-i) fw[i] += x;
      |         ~^~~~~~~~~~

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