제출 #836115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836115		penguinman	Arranging Shoes (IOI19_shoes)	C++17	85 / 100	41 ms	12800 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;
	rep(i,0,N){
		if(s[i] > 0) continue;
		ll val = -s[i];
		p[now++] = i;
		p[now++] = idx[val].back();
		idx[val].pop_back();
	}
	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: 0 / 15