Submission #809122

#	Time	Username	Problem	Language	Result	Execution time	Memory
809122		Username4132	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	48 ms	15012 KiB

shoes

#include "shoes.h"
#include<iostream>
#include<vector>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back

const int MAXN = 100010;
bool del[2*MAXN];
int n, bit[2*MAXN];
vector<int> ubs[2*MAXN];

int sum(int r){
	int ret=0;
	for(; r>=0; r=(r&(r+1))-1) ret+=bit[r];
	return ret;
}

void update(int r, int delta){
	for(; r<2*MAXN; r=r|(r+1)) bit[r]+=delta;
}

long long count_swaps(vector<int> s) {
	n = s.size()>>1;
	ll ret=0;
	dforn(i, 2*n) ubs[n+s[i]].PB(i);
	forn(i, 2*n) if(!del[i]){
		int assi = ubs[n-s[i]].back();
		ubs[n+s[i]].pop_back();
		ubs[n-s[i]].pop_back();
		del[i]=del[assi]=true;
		ret+=(assi-i-1-sum(assi-1)+sum(i) + (s[i]>0));
		update(i, 1), update(assi, 1);
	}
	return ret;
}

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