Submission #153410

#	Time	Username	Problem	Language	Result	Execution time	Memory
153410		nandonathaniel	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	106 ms	18936 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const LL MAXN=100005;
vector<LL> neg[MAXN],pos[MAXN];
pii arr[MAXN];
LL sh[2*MAXN],bit[2*MAXN],n;

void update(LL val){
	for(LL i=val;i<=2*n;i+=(i&(-i)))bit[i]++;
}

LL query(LL val){
	LL ans=0;
	for(LL i=val;i>0;i-=(i&(-i)))ans+=bit[i];
	return ans;
}

long long count_swaps(vector<int> s) {
	n=(LL)s.size()/2;
	for(LL i=0;i<s.size();i++){
		if(s[i]<0)neg[abs(s[i])].push_back(i+1);
		else pos[s[i]].push_back(i+1);
	}
	LL now=0;
	for(LL i=1;i<=n;i++){
		for(int j=0;j<neg[i].size();j++){
			now++;
			arr[now]={min(neg[i][j],pos[i][j]),max(neg[i][j],pos[i][j])};
		}
	}
	LL ans=0;
	sort(arr+1,arr+n+1);
	for(LL i=1;i<=n;i++){
		if(s[arr[i].first-1]<0){
			sh[2*i-1]=arr[i].first;
			sh[2*i]=arr[i].second;
		}
		else{
			sh[2*i-1]=arr[i].second;
			sh[2*i]=arr[i].first;
		}
	}
	for(LL i=1;i<=2*n;i++){
		ans+=(sh[i]-1-query(sh[i]));
		update(sh[i]);
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:23:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(LL i=0;i<s.size();i++){
             ~^~~~~~~~~
shoes.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<neg[i].size();j++){
               ~^~~~~~~~~~~~~~

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