Submission #298192

#	Time	Username	Problem	Language	Result	Execution time	Memory
298192		Abelyan	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	113 ms	38768 KiB

shoes

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

#define FOR(i,n) for (int i=0;i<(n);++i)


const int N=1e6+6;
priority_queue<int> mn[N],d;
int fw[N];
int n;
int get(int ind){
	int ans=0;
	for(;ind>=0;ind=(ind&(ind+1))-1){
		ans+=fw[ind];
	}
	return ans;
}

void add(int ind,int val){
	for(;ind<n;ind=ind|(ind+1)){
		fw[ind]+=val;
	}
}

long long count_swaps(vector<int> s) {
	n=s.size();
	FOR(i,n){
		if (s[i]<0){
			d.push(-i);
		}
		else{
			mn[s[i]].push(-i);
		}
	}
	long long ans=0;
	FOR(i,n/2){
		int a=-d.top();
		d.pop();
		//cout<<a<<endl;
		int b=-mn[-s[a]].top();
		mn[-s[a]].pop();
		//cout<<a<<" "<<b<<endl;
		if (b<a)ans++;
		ans+=a+b-4*i-1+get(a)+get(b);
		//cout<<ans<<endl;
		add(a,-1);
		add(b,-1);
		add(0,2);
		
		//cout<<a<<" "<<b<<endl;
	}
	return ans;
}

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