제출 #836102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836102		penguinman	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	40 ms	14068 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 count_swaps(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]));
	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: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15