Submission #1153298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153298		owoovo	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1096 ms	328 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
ll bit[200010];
void modify(ll x,int p){
	while(p<200005){
		bit[p]+=x;
		p+=p&(-p);
	}
	return;
}
ll query(int p){
	ll ans=0;
	while(p){
		ans+=bit[p];
		p-=p&(-p);
	}
	return ans;
}
int id[200010],n,pos[200010],cnt;
ll count_swaps(vector<int> s) {
	ll ans=0;
	cnt=1;
	n=s.size()/2;
	for(int i=0;i<s.size();i++){
		id[s[i]+n]=i+1;
		if(id[-s[i]+n]){
			int now=abs(s[i]);
			pos[id[-now+n]]=cnt;
			pos[id[now+n]]=cnt+1;
			cnt+=2;
			id[now+n]=0;
			id[-now+n]=0;
		}
	}
	for(int i=1;i<=2*n;i++){
		ans+=query(2*n)-query(pos[i]);
		modify(1,pos[i]);
	}
	return ans;
}

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