Submission #399270

#	Time	Username	Problem	Language	Result	Execution time	Memory
399270		_Avocado_	Arranging Shoes (IOI19_shoes)	C++14	15 / 100	979 ms	166432 KiB

shoes

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define int int64_t

vector<int>seg;

void update(int k, int v, int pos, int l, int r){
	if(l == r){
		seg[pos] = v;
		return;
	}
	else if(k <= (l+r)/2) update(k, v, pos*2, l, (r+l)/2);
	else update(k, v, pos*2+1, (l+r)/2+1, r);
	
	seg[pos] = seg[pos*2] + seg[pos*2+1];
}

int query(int ql, int qr, int pos, int l, int r){
	if(l >= ql && r <= qr) return seg[pos];
	else if(l > qr || r < ql) return 0;
	else return query(ql, qr, pos*2, l, (l+r)/2) + query(ql, qr, pos*2+1, (l+r)/2+1, r);
}

int solve1(vector<int>&shoes, int n){
	vector<vector<int>>fred(n);
	seg.assign(n*4, 0);
	
	for(int i = 0; i<n; ++i){
		fred[i] = {shoes[i], i};
	}
	
	sort(fred.begin(), fred.end());
	reverse(fred.begin(), fred.end());
	
	int ans = 0;
	
	for(int i = 0; i<n; ++i){
		ans += query(0, fred[i][1]-1, 1, 0, n-1);
		update(fred[i][1], 1, 1, 0, n-1);
	}
	
	return ans;
}

int solve2(vector<int>&shoes, int n){
	vector<vector<int>>fred(n);
	seg.assign(n*4, 0);
	
	for(int i = 0; i<n; ++i){
		fred[i] = {shoes[i], i};
	}
	
	sort(fred.begin(), fred.end());
	//reverse(fred.begin(), fred.end());
	
	int ans = 0;
	
	for(int i = 0; i<n; ++i){
		ans += query(0, fred[i][1]-1, 1, 0, n-1);
		update(fred[i][1], 1, 1, 0, n-1);
	}
	
	return ans;
}


long long count_swaps(std::vector<int32_t>v){
	int n = v.size();
	
	map<int, queue<int>>mp;
	vector<int>shoes1(n);
		
	int cur = 1;
	
	for(int i = 0; i<n; ++i){
		if(v[i] < 0){
			mp[v[i]].push(cur);
			shoes1[i] = cur;
			cur += 2;
		}
	}
		
	
	for(int i = 0; i<n; ++i){
		if(v[i] > 0){
			shoes1[i] = mp[-v[i]].front()+1;
			mp[-v[i]].pop();
		}
	}
	
	vector<int>shoes2(n);

	cur = 2;
		
	for(int i = 0; i<n; ++i){
		if(v[i] > 0){
			mp[v[i]].push(cur);
			shoes2[i] = cur;
			cur += 2;
		}
	}
		
	for(int i = 0; i<n; ++i){
		if(v[i] < 0){
			shoes2[i] = mp[-v[i]].front()-1;
			mp[-v[i]].pop();
		}
	}
		
	
	//for(auto u: shoes) cout<<u<<" ";
	//cout<<endl;
	
	int one = min(solve1(shoes1, n), solve2(shoes1, n));;
	int two = min(solve1(shoes2, n), solve2(shoes2, n));

	return min(one, two);
}

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