제출 #171363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171363		Xellos	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	156 ms	15880 KiB

shoes

#include "shoes.h"

class fin {
	std::vector<int> T;
	
	int lastone(int x) { return x & (x ^ (x-1)); }

public:
	fin(int N) : T(N+1, 0) {}

	void put(int pos, int val) {
		for(int i = pos+1; i < (int)T.size(); i += lastone(i))
			T[i] += val;
	}

	int get(int pos) {
		int ret = 0;
		for(int i = pos+1; i > 0; i -= lastone(i))
			ret += T[i];
		return ret;
	}
};

long long count_swaps(std::vector<int> S) {
	int N = S.size()/2;
	std::vector<int> pos_l[100010], pos_r[100010];
	for(int i = 0; i < 2*N; i++) {
		if(S[i] < 0) pos_l[-S[i]].push_back(i);
		else pos_r[S[i]].push_back(i);
	}
	long long ret = 0;
	std::vector<int> next(2*N, 0);
	for(int i = 1; i <= N; i++)
		for(int j = 0; j < (int)pos_l[i].size(); j++)
			next[std::min(pos_l[i][j], pos_r[i][j])] = std::max(pos_l[i][j], pos_r[i][j]);
	fin F(2*N);
	for(int i = 0; i < 2*N; i++) F.put(i, 1);
	std::vector<char> live(2*N, 1);
	for(int i = 0; i < 2*N; i++) if(next[i]) {
		ret += F.get(next[i]-1) - F.get(i);
		F.put(next[i], -1);
	}
	for(int i = 1; i <= N; i++)
		for(int j = 0; j < (int)pos_l[i].size(); j++)
			if(pos_l[i][j] > pos_r[i][j]) ret++;
	return ret;
}

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