Submission #159127

#	Time	Username	Problem	Language	Result	Execution time	Memory
159127		kig9981	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	110 ms	16628 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> L[100001], R[100001];
int tree[200001];

void update(int n, int v)
{
	for(++n;n<=200000;n+=n&-n) tree[n]+=v;
}

int get_cnt(int n)
{
	int ret=0;
	for(++n;n;n-=n&-n) ret+=tree[n];
	return ret;
}

long long count_swaps(vector<int> S)
{
	int N=S.size();
	priority_queue<tuple<int,int,int>> Q;
	long long ret=0;
	for(int i=N-1;i>=0;i--) {
		if(S[i]>0) R[S[i]].push_back(i);
		else L[-S[i]].push_back(i);
		update(i,1);
	}
	for(int i=N/2;i;i--) for(int j=0;j<L[i].size();j++) Q.emplace(-L[i][j]-R[i][j],L[i][j],R[i][j]);
	while(!Q.empty()) {
		auto[s,i,j]=Q.top();
		Q.pop();
		update(i,-1);
		ret+=get_cnt(i);
		update(j,-1);
		ret+=get_cnt(j);
	}
	return ret;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:31:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=N/2;i;i--) for(int j=0;j<L[i].size();j++) Q.emplace(-L[i][j]-R[i][j],L[i][j],R[i][j]);
                                   ~^~~~~~~~~~~~
shoes.cpp:33:13: warning: unused variable 's' [-Wunused-variable]
   auto[s,i,j]=Q.top();
             ^

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