Submission #578691

#	Time	Username	Problem	Language	Result	Execution time	Memory
578691		MrDeboo	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	601 ms	275364 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int seg[600000];
int n,N,L,R;
int slv(int l=1,int r=N,int in=1){
    if(l>R||r<L)return 0;
    if(l>=L&&r<=R)return seg[in];
    int mid=(l+r)/2;
    return slv(l,mid,in*2)+slv(mid+1,r,in*2+1);
}
void upd(int in){
	in=in+N;
	seg[in]=0;
	in/=2;
	while(in){
		seg[in]=seg[in*2]+seg[in*2+1];
		in/=2;
	}
}
long long count_swaps(vector<int> s){
	n=s.size();
	N=exp2(ceil(log2(n)));
	long long ans=0;
	deque<int>dq[2][n+1];
	for(int i=0;i<n;i++)dq[s[i]>0][abs(s[i])].push_back(i);
	for(int i=0;i<N;i++)seg[i+N]=1;
	for(int i=N-1;i;i--)seg[i]=seg[i*2]+seg[i*2+1];
	L=1;
	for(int i=0;i<n/2;i++){
		int l=0,r=n-1,mid,f=0;
		while(l<=r){
			mid=(l+r)/2;
			R=mid+1;
			if(slv()==0)l=mid+1;
			else{r=mid-1;f=mid;}
		}
		int k=abs(s[f]);
		R=dq[0][k][0];
		dq[0][k].pop_front();
		if(R>=1)ans+=slv();
		upd(R);
		R=dq[1][k][0];
		dq[1][k].pop_front();
		if(R>=1)ans+=slv();
		upd(R);
	}
	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