Submission #303188

#	Time	Username	Problem	Language	Result	Execution time	Memory
303188		sofapuden	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	105 ms	16884 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

bool com(pair<int,int> a, pair<int,int> b){
	return min(a.first,a.second)<min(b.first,b.second);
}
vector<int> tree;
vector<int> ind;

void build(int l, int r, int p){
	if(l == r)ind[l] = p;
	else{
		build(l,(l+r)/2,p*2);
		build((l+r)/2+1,r,p*2+1);
	}
}
void add(int r, int p, int lb, int rb){
	if(rb <= r){tree[p]++;return;}
	if(lb > r)return;
	add(r,p*2,lb,(rb+lb)/2);
	add(r,p*2+1,(rb+lb)/2+1,rb);
}
int check(int p){
	if(p == 0)return 0;
	return check(p/2)+tree[p];
}
ll count_swaps(vector<int> s) {
	int n = s.size()/2;
	tree.resize(8*n);
	ind.resize(n*2+1);
	build(0,n*2-1,1);
	vector<vector<pair<int,int>>> shoe(n*2+1);
	vector<pair<int,int>> seg;
	vector<int> num(n*2+1,0);
	for(int i = 0; i < n*2; ++i){
		if(num[abs(s[i])] == (int)shoe[abs(s[i])].size()){
			shoe[abs(s[i])].push_back({s[i],i});
			continue;
		}
		if(shoe[abs(s[i])][num[abs(s[i])]].first == s[i]){
			shoe[abs(s[i])].push_back({s[i],i});
			continue;
		}
		if(s[i] > 0)seg.push_back({i,shoe[abs(s[i])][num[abs(s[i])]].second});
		else seg.push_back({shoe[abs(s[i])][num[abs(s[i])]].second,i});
		num[abs(s[i])]++;
	}
	sort(seg.begin(),seg.end(),com);
	ll ans = 0;
	for(int i = 0; i < (int)seg.size(); ++i){
		int x = max(seg[i].first,seg[i].second);
		int y = x+check(ind[x]);
		add(x,1,0,n*2-1);
		ans+=y-(i*2+1);
		ans+=seg[i].first < seg[i].second;		
	}
	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