제출 #399428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399428		mshandilya	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	152 ms	141660 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

long long count_swaps(std::vector<int> s) {
	int n = s.size()/2, orientation_swaps = 0;
	long long total_swaps, pairing_swaps = 0;
	std::vector<int> pair_index(2*n), prefix1(2*n), prefix2(2*n), prefix3(2*n), BIT_used(n);
	std::vector<queue<int>> left_shoe(n), right_shoe(n);
	//task 1 : forming pairs
	for(int i = 0; i<2*n; i++) {
		if(s[i]>0) {
			if(!left_shoe[s[i]-1].empty()) {
				pair_index[left_shoe[s[i]-1].front()] = i+1;
				left_shoe[s[i]-1].pop();
			}
			else
				right_shoe[s[i]-1].push(i);
		}
		else {
			if(!right_shoe[abs(s[i])-1].empty()) {
				pair_index[right_shoe[abs(s[i])-1].front()] = i+1;
				right_shoe[abs(s[i])-1].pop();
				orientation_swaps++;
			}
			else
				left_shoe[abs(s[i])-1].push(i);
		}
	}
	//task 2 : forming prefix1 of "second shoe in pairs before me"
	for(int i = 0, count1 = 0, count2 = 0; i<2*n; i++) {
		prefix1[i] = count1;
		prefix2[i] = count2;
		if(pair_index[i])
			count2++;
		else
			count1++;
	}
	//task 3 : finding prefix3 of "used second shoe in pair before me for each second shoe in pair"
	for(int i = 0, j; i<2*n; i++) {
		if(pair_index[i]) {
			j = prefix1[pair_index[i]-1];
			while(j>0) {
				prefix3[pair_index[i]-1] += BIT_used[j-1];
				j -= (j & (-j));
			}
			j = prefix1[pair_index[i]-1] + 1;
			while(j<=n) {
				BIT_used[j-1]++;
				j += (j & (-j));
			}
		}
	}
	//task 4 : finding swaps for pairing
	for(int i = 0; i<2*n; i++)
		if(pair_index[i])
			pairing_swaps += pair_index[i]-prefix2[pair_index[i]-1]+prefix2[i]+prefix1[pair_index[i]-1]-prefix3[pair_index[i]-1]-i-1;
	total_swaps = pairing_swaps + orientation_swaps;
	return total_swaps;
}

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