Submission #382462

#	Time	Username	Problem	Language	Result	Execution time	Memory
382462		mariowong	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	318 ms	140008 KiB

shoes

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

using namespace std;

int n,pos[200005],now,pt;
long long ans;
queue <int> v[200005];
vector <int> ct,d;
void cntInv(int l,int r){
	if (l == r);
	else
	{
		int mid=(l+r)/2;
		ct.clear(); d.clear(); 
		for (int i=l;i<=mid;i++){
			ct.push_back(pos[i]);
		}
		sort(ct.begin(),ct.end()); reverse(ct.begin(),ct.end()); 
		for (int i=mid+1;i<=r;i++){
			d.push_back(pos[i]);
		}
		sort(d.begin(),d.end()); reverse(d.begin(),d.end()); 
		pt=0; 
		for (int i=0;i<d.size();i++){
			while (pt < (int)ct.size() && ct[pt] >= d[i])
			pt++;
			ans+=pt;
		}
		cntInv(l,mid);
		cntInv(mid+1,r);
	}
}
long long count_swaps(std::vector<int> s) {
	n=(long long)s.size(); 
	for (int i=0;i<n;i++){
		if (v[100000-s[i]].empty())
		v[s[i]+100000].push(i);
		else
		{
			if (s[v[100000-s[i]].front()] < 0){
				pos[v[100000-s[i]].front()]=now;
				pos[i]=now+1;
			}
			else
			{
				pos[v[100000-s[i]].front()]=now+1;
				pos[i]=now;
			}
			now+=2;
			v[100000-s[i]].pop();
		}
	}
	cntInv(0,n-1);
	return ans;
}
/*int r,x;
vector <int> ori;
int main(){
	cin >> r;
	for (int i=0;i<2*r;i++){
		cin >> x;
		ori.push_back(x);
	}
	cout << count_swaps(ori) << "\n";
}*/

Compilation message (stderr)

shoes.cpp: In function 'void cntInv(int, int)':
shoes.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for (int i=0;i<d.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