제출 #1047356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1047356		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	32 ms	8780 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

struct fenwick{
	int n;
	vector<int> fen;
	fenwick(int n) : n(n), fen(n){}

	void upd(int pos, int val){
		for(; pos < n; pos |= pos + 1)
			fen[pos] += val;
	}

	int index(int ind){
		int ret = 0;
		for(; ind >= 0; ind = (ind & (ind + 1)) - 1)
			ret += fen[ind];
		return ret;
	}
};

ll count_swaps(vector<int> v){
	int n = v.size() / 2;
	vector<int> negative;
	vector<vector<int>> occurence(n + 1);

	for(int i = 2 * n - 1; i >= 0; i--){
		if(v[i] < 0) negative.pb(i);
		else occurence[v[i]].pb(i);
	}

	fenwick fen(2 * n);
	ll ans = 0;

	for(int i = 0; i < 2 * n; i++)
		fen.upd(i, 1);

	for(int i = 0; i < n; i++){
		int neg = negative.back(); negative.pop_back();
		int val = v[neg];
		fen.upd(neg, -1);
		neg = fen.index(neg);
		ans += neg;

		int pos = occurence[-val].back();
		occurence[-val].pop_back();
		fen.upd(pos, -1);
		pos = fen.index(pos);
		ans += pos;
	}
	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