Submission #1067886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067886		pcc	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	109 ms	141520 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 2e5+10;
const int sh = mxn>>1;
int pos[mxn],tar[mxn];
int arr[mxn];
int N;

deque<int> dq[mxn];

struct BIT{
	int bit[mxn];
	void modify(int p,int v){
		p++;
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	int getval(int p){
		p++;
		int re = 0;
		for(;p>0;p-= p&-p)re += bit[p];
		return re;
	}
};

BIT bit;

long long count_swaps(std::vector<int> s) {
	N = s.size();
	for(int i = 0;i<N;i++)arr[i] = s[i];
	iota(pos,pos+N,0);
	memset(tar,-1,sizeof(tar));
	for(int i = N-1;i>=0;i--){
		//cerr<<i<<":"<<arr[i]<<endl;
		if(dq[sh-arr[i]].size()){
			tar[i] = dq[sh-arr[i]][0];
			dq[sh-arr[i]].pop_front();
		}
		else dq[sh+arr[i]].push_back(i);
	}
	ll ans = 0;
	for(int i = N-1;i>=0;i--){
		if(tar[i] == -1)continue;
		if(arr[i]>0)ans++;
		int s = i,e = tar[i];
		//cerr<<s<<','<<e<<endl;
		ans += (e-bit.getval(e))-s-1;
		bit.modify(s,1);
		bit.modify(e+1,-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