| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1232480 | nibert | 나일강 (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include "nile.h"
using namespace std;
struct dsu {
vector<int> parent, rank;
dsu (int n) {
parent.resize(n,-1);
rank.resize(n,1);
}
int find(int x) {
return(parent[x]== -1) ? x: (parent[x] = find(parent[x]));
}
void merge(int u, int v){
int rootU = find(u);
int rootV = find(v);
if(rootU != rootV) {
if(rank[rootU] > rank[rootV]) {
parent[rootV] = rootU;
}
else if (rank[rootU] < rank[rootV]) {
parent[rootU] = rootV;
}
else {
parent[rootV] = rootU;
rank[rootU]++;
}
}
}
};
int find_best_pair(const vector<int> &w, int left, int d) {
int low = left + 1, high = w.size()-1;
int best = -1;
while (low <= high){
int mid = (low+high) /2;
if(w[mid]-w[left] <=d){
if(best == -1 || w[mid] - w[left] < w[best] - w[left]) {
best = mid;
}
high = mid -1;
}
else{
high = mid - 1;
}
}
return best;
}
int boat_count(vector<int> w, int d) {
int N = w.size();
sort(w.begin(), w.end());
dsu boats(N);
vector <bool> paired(N,false);
for (int i = 0; i < N; i ++) {
if(paired[i]) {
continue;
}
int best_pair = find_best_pair(w,i,d);
if(best_pair != -1) {
boats.merge(i,best_pair);
paired[best_pair] = true;
}
}
int boat_count = 0;
for(int i = 0; i < N; i++) {
if(boats.find(i) == i){
boat_count++;
}
}
return boat_count;
}