Submission #824431

#	Time	Username	Problem	Language	Result	Execution time	Memory
824431		tomruk	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	186 ms	30992 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct BIT{
	vector<int> bit;
	int n;
	BIT(int sz){
		n = sz + 5;
		bit.assign(n,0);
	}
	void upd(int pos,int val){
		for(;pos<n;pos += pos & -pos){
			bit[pos] += val;
		}
	}
	int get(int pos){
		int ret = 0;
		for(;pos > 0;pos -= pos & -pos){
			ret += bit[pos];
		}
		return ret;
	}
	int get(int l,int r){
		return get(r) - get(l-1);
	}
};
long long count_swaps(vector<int> a){
	int n = a.size()/2;
	long long ans = 0;
	BIT bt(2*n);
	set<int> s;
	set<int> pos[n+1][2];
	for(int i = 0;i<2*n;i++){
		s.insert(i);
		pos[abs(a[i])][a[i] > 0].insert(i);
	}
	for(int i = 0;i<n;i++){
		int val1 = 1e9;
		int val2 = 1e9;
		int num1 = a[*s.begin()];
		int num2 = a[*next(s.begin())];
		int pos1 = *s.begin() + bt.get(*s.begin() + 1,2*n);
		int pos2 = *next(s.begin()) + bt.get(*next(s.begin()) + 1,2*n);
		int pos3 = *pos[abs(num1)][num1 < 0].begin() + bt.get(*pos[abs(num1)][num1 < 0].begin() + 1,2*n);
		int pos4 = *pos[abs(num2)][num2 < 0].begin() + bt.get(*pos[abs(num2)][num2 < 0].begin() + 1,2*n);
		//cout << pos1 << ' ' << pos2 << ' ' << pos3 << ' ' << pos4 << endl;
		val1 = pos3 - pos1  - 1  + (num1 > 0);
		if(pos2 < pos4)
			val2 = pos4 - (pos2-1) + (num2 > 0);
		//cout << val1 << ' ' << val2 << endl;
		if(val1 < val2){
			ans += val1;
			int x = *s.begin();
			int y = *pos[abs(num1)][num1 < 0].begin();
			s.erase(x);
			s.erase(y);
			bt.upd(x + 1,1);
			bt.upd(y + 1,1);
			pos[abs(a[x])][a[x] > 0].erase(x);
			pos[abs(a[y])][a[y] > 0].erase(y);
		}
		else{
			ans += val2;
			int x = *next(s.begin());
			int y = *pos[abs(num2)][num2 < 0].begin();
			s.erase(x);
			s.erase(y);
			bt.upd(x + 1,1);
			bt.upd(y + 1,1);
			pos[abs(a[x])][a[x] > 0].erase(x);
			pos[abs(a[y])][a[y] > 0].erase(y);
		}
	}
	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