Submission #759030

#	Time	Username	Problem	Language	Result	Execution time	Memory
759030		dsyz	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	204 ms	275024 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll = long long;
#define MAXN (200005)
bool done[MAXN];
deque<ll> Left[MAXN];
deque<ll> Right[MAXN];
ll fw[MAXN];
void update(ll x,ll nval) {
	x++;
	for(;x<MAXN;x+=x&(-x)) fw[x]+=nval;
}
ll aaa(ll x) {
	x++;
	ll res = 0;
	for(;x;x-=x&(-x)) res += fw[x];
	return res;
}
ll sum(ll a,ll b) {
	return aaa(b) - aaa(a-1);
}

long long count_swaps(std::vector<int> s) {
	ll ans = 0;
	for(ll i = 0;i < s.size();i++){
		if(s[i] < 0) Left[abs(s[i])].push_back(i);
		else if(s[i] > 0) Right[abs(s[i])].push_back(i);
	}
	for(ll i = 0;i < s.size();i++){
		if(done[i]) continue;
		ll siz = abs(s[i]);
		if(s[i] < 0){ //left shoe
			ll Lshoe = i;
			ll Rshoe = Right[siz].front();
			ll subtract = sum(Lshoe + 1,Rshoe);
			ans += (Rshoe - Lshoe - 1) - subtract;
			update(Rshoe,1);
			done[Lshoe] = 1;
			done[Rshoe] = 1;
			Left[siz].pop_front();
			Right[siz].pop_front();
		}else if(s[i] > 0){ //right shoe
			ll Lshoe = Left[siz].front();
			ll Rshoe = i;
			ll subtract = sum(Rshoe,Lshoe);
			ans += (Lshoe - Rshoe) - subtract;
			update(Lshoe,1);
			done[Lshoe] = 1;
			done[Rshoe] = 1;
			Left[siz].pop_front();
			Right[siz].pop_front();
		}
	}
	return ans;
}

Compilation message (stderr)

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