제출 #1151871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151871		Pacybwoah	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	48 ms	4520 KiB

shoes

#include "shoes.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
namespace{
	struct BIT{
		vector<int> bit;
		int n;
		BIT(int _n){
			n = _n;
			bit.resize(n + 1);
		}
		void modify(int pos, int val){
			while(pos <= n){
				bit[pos] += val;
				pos += (pos & -pos);
			}
		}
		int query(int pos){
			int ans = 0;
			while(pos > 0){
				ans += bit[pos];
				pos -= (pos & -pos);
			}
			return ans;
		}
	};
}

long long count_swaps(std::vector<int> s) {
	ll ans = 0;
	int n = (int)s.size() / 2;
	vector<pair<int, int>> cp;
	for(int i = 0; i < 2 * n; i++){
		if(s[i] > 0) cp.emplace_back(s[i], i);
	}
	sort(cp.begin(), cp.end());
	for(int i = 0; i < n; i++){
		s[cp[i].second] = i + 1;
	}
	vector<pair<int, int>>().swap(cp);
	for(int i = 0; i < 2 * n; i++){
		if(s[i] < 0) cp.emplace_back(-s[i], i);
	}
	sort(cp.begin(), cp.end());
	for(int i = 0; i < n; i++){
		s[cp[i].second] = -(i + 1);
	}
	BIT bit(2 * n);
	for(int i = 1; i <= 2 * n; i++) bit.modify(i, 1);
	vector<pair<int, int>> pos(n + 1);
	for(int i = 0; i < 2 * n; i++){
		if(s[i] < 0) pos[-s[i]].first = i + 1;
		else pos[s[i]].second = i + 1;
	}
	auto cmp = [&](pair<int, int> a, pair<int, int> b){
		return a.first + a.second < b.first + b.second;
	};
	sort(next(pos.begin()), pos.end(), cmp);
	for(int i = 1; i <= n; i++){
		if(pos[i].first > pos[i].second) ans++;
		ans += bit.query(pos[i].first) + bit.query(pos[i].second) - 3;
		bit.modify(pos[i].first, -1);
		bit.modify(pos[i].second, -1);
	}
	return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run shoes.cpp grader.cpp

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