제출 #1163246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163246		boclobanchat	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	202 ms	149172 KiB

shoes

#include"shoes.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int fen[MAXN],V[MAXN],pos[MAXN];
stack<int> vi[MAXN];
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
long long count_swaps(vector<int> s)
{
	int n=s.size();
	for(int i=n-1;i+1;i--) vi[s[i]+n/2].push(i);
	set<int> st;
	for(int i=0;i<n;i++) st.insert(i);
	for(int i=0;i<n/2;i++)
	{
		int p=*st.begin(),q=vi[-s[p]+n/2].top();
		vi[s[p]+n/2].pop(),vi[s[q]+n/2].pop();
		if(s[p]<0) V[i*2]=p+1,V[i*2+1]=q+1;
		else V[i*2]=q+1,V[i*2+1]=p+1;
		st.erase(p),st.erase(q);
	}
	for(int i=0;i<n;i++) pos[V[i]]=i+1;
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=pos[i]+get(n)-get(pos[i])-i;
		update(pos[i],n,1);
	}
	return ans;
}

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