Submission #1230461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230461		altern23	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	324 KiB

shoes

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

#define ll long long

struct BIT{
	ll N;
	vector<ll> bit;
	BIT(ll _n){
		N = _n;
		bit.resize(N + 5);
	}
	
	void upd(ll idx, ll val){
		idx++;
		for(; idx <= N; idx += idx & -idx) bit[idx] += val;
	}
	ll get(ll idx){
		idx++;
		ll ans = 0;
		for(; idx >= 1; idx -= idx & -idx) ans += bit[idx];
		return ans;
	}
	ll query(ll l, ll r) { return get(r) - get(l - 1); }
};

long long count_swaps(vector<int> s) {
	int N = (int)s.size( ) / 2;
	vector<int> kiri[N + 5], kanan[N + 5];
	vector<int> vis(2 * N + 5);
	int ans = 0;
	
	BIT bit(2 * N);
	for(int i = 1; i < 2 * N; i++) bit.upd(i, 1);
	for(int i = 0; i < 2 * N; i++){
		if(vis[i]) continue;
		if(s[i] < 0){
			if(!kanan[abs(s[i])].size()){
				kiri[abs(s[i])].push_back(i);
				continue;
			}
			ans += abs(bit.get(i) - bit.get(kanan[abs(s[i])].back())) - 1;
			vis[i] = 1, vis[kanan[abs(s[i])].back()] = 1;
			bit.upd(kanan[abs(s[i])].back(), 1);
			bit.upd(i, -1);
			kanan[abs(s[i])].pop_back();
		}
		else{
			if(!kiri[abs(s[i])].size()){
				kanan[abs(s[i])].push_back(i);
				continue;
			}
			ans += abs(bit.get(i) - bit.get(kiri[abs(s[i])].back()));
			vis[i] = 1, vis[kiri[abs(s[i])].back()] = 1;
			bit.upd(kiri[abs(s[i])].back(), 1);
			bit.upd(i, -1);
			kiri[abs(s[i])].pop_back();
		}
	}
	
	return ans;
}

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