Submission #836128

#	Time	Username	Problem	Language	Result	Execution time	Memory
836128		penguinman	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	50 ms	16588 KiB

shoes

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


using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple

constexpr ll inf = (1ll<<60);

struct binary_indexed_tree{
	vi node;
	ll N;
	binary_indexed_tree(int n): N(n){
		node.resize(N+1);
	}
	void add(ll idx, ll val){
		idx++;
		for(; idx<=N; idx+=(idx&-idx)) node[idx] += val;
	}
	ll sum(ll idx){
		idx++;
		ll ret = 0;
		for(; 0<idx; idx-=(idx&-idx)) ret += node[idx];
		return ret;
	}
};

long long subtask_2_5(std::vector<int> s) {
	ll N = s.size();
	vii idx(N+1);
	rep(i,0,N){
		if(s[i] > 0) idx[s[i]].pb(i);
	}
	REP(i,0,N) reverse(all(idx[i]));
	vector<bool> used(N);
	binary_indexed_tree bit(N+1);
	rep(i,0,N) bit.add(i,1);
	ll ans = 0;
	rep(i,0,N/2){
		ll min = inf;
		rep(j,0,N){
			if(used[j]) continue;
			if(s[j] > 0) continue;
			ll val = -s[j];
			ll cost = bit.sum(j)-1;
			ll p = idx[val].back();
			cost += bit.sum(p)-1;
			if(j < p) cost--;
			min = std::min(min, cost);
		}
		ans += min;
		rep(j,0,N){
			if(used[j]) continue;
			if(s[j] > 0) continue;
			ll val = -s[j];
			ll cost = bit.sum(j)-1;
			ll p = idx[val].back();
			cost += bit.sum(p)-1;
			if(j < p) cost--;
			if(min == cost){
				used[j] = used[p] = true;
				bit.add(j,-1);
				bit.add(p,-1);
				idx[val].pop_back();
				break;
			}
		}
	}
	return ans;
}

long long count_swaps(std::vector<int> s) {
	ll N = s.size();
	//if(N/2 <= 1000) return subtask_2_5(s);
	vii idx(N+1);
	rep(i,0,N){
		if(s[i] > 0) idx[s[i]].pb(i);
	}
	REP(i,0,N) reverse(all(idx[i]));
	vi p(N);
	ll now = 0;
	vector<std::tuple<ll,ll,ll>> data;
	rep(i,0,N){
		if(s[i] > 0) continue;
		ll val = -s[i];
		ll cost = i+idx[val].back();
		if(i < idx[val].back()) cost--;
		data.pb(mtp(cost, i, idx[val].back()));
		idx[val].pop_back();
	}
	sort(all(data));
	for(auto el: data){
		ll x,y,z; std::tie(x,y,z) = el;
		p[now++] = y;
		p[now++] = z;
	}
	ll ans = 0;
	binary_indexed_tree bit(N);
	rep(i,0,N){
		ans += i-bit.sum(p[i]);
		bit.add(p[i],1);
	}
	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