Submission #1316883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316883		exoworldgd	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	454 ms	146772 KiB

shoes

#include<bits/stdc++.h>
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
ll count_swaps(vector<int>s) {
	int n=s.size(),ans=0,t[n+1]={};
	map<int,queue<int>>mp;
	for(int i=0,x,pos;i<n;i++){
		if(mp[-s[i]].empty())pos=i+1,mp[s[i]].push(pos);
		else{
			pos=mp[-s[i]].front(),mp[-s[i]].pop(),ans+=i;
			for(int j=pos;j>0;j-=j&-j)ans-=t[j];
			ans+=x<0;
		}
		for(;pos<=n;pos+=pos&-pos)t[pos]++;
	}
	return ans;
}

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