제출 #1316885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316885		exoworldgd	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	453 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(std::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++){
		x=s[i];
		if(mp[-x].empty())pos=i+1,mp[x].push(pos);
		else{
			pos=mp[-x].front(),mp[-x].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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15