Submission #605506

#	Time	Username	Problem	Language	Result	Execution time	Memory
605506		misteg168	Arranging Shoes (IOI19_shoes)	C++17	70 / 100	1090 ms	37780 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second

ll get(ll x){
	ll y = 0;
	while((1ll<<y) < x) y++;
	return (1ll << y);
}

void upd(vector<ll> & segtree, ll a, ll t){
	a += t;
	while(a > 0){
		segtree[a]++;
		a/=2;
	}
}

ll rg(vector<ll> & segtree, ll a, ll b, ll t){
	a += t, b += t;
	ll ans = 0;
	while(a <= b){
		if(a % 2 == 1) ans += segtree[a++];
		if(b % 2 == 0) ans += segtree[b--];
		a /= 2, b/= 2;
	}
	return ans;
}

long long count_swaps(std::vector<int> s) {
	ll n = s.size();
	map<ll, set<ll>> v;
	for(int i = 0; i < n; i++){
		v[-s[i]].insert(i);
	}
	ll t = get(n);
	vector<ll> segtree(2*t);
	vector<bool> pos(n, 0);
	ll ans = 0;
	for(int i = 0; i < n; i++){
		if(pos[i]){
			continue;
		}
		ans += *(v[s[i]].begin())-i-rg(segtree, i, *(v[s[i]].begin()), t);
		if(s[i] < 0) ans--; //not need to swap shoes
		cerr << i << " " << *v[ s[i] ].begin() << " " << ans << "\n";
		pos[i] = 1;
		upd(segtree, *(v[s[i]].begin()) , t);
		pos[ *(v[s[i]].begin()) ] = 1;
		v[ s[*v[ s[i] ].begin()] ].erase(i);
		v[ s[i] ].erase( *v[ s[i] ].begin());

		//~ for(auto x : v){
			//~ cout << x.F << "\n";
			//~ for(auto y : x.S) cout << y << " ";
			//~ cout << "\n";
		//~ }
		//~ cout << "\n";
	}
	
	return ans;
}

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