#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
vector<int>arr;
bool pos(ll s,ll ride){
	if(s<arr.back()) return 0;
	ll r = 0;
	multiset<int>st(arr.begin(),arr.end());
	while(st.size()){
		r++;
		int cur = *st.begin();
		if(cur>s) return 0;
		st.erase(st.begin());
		if(st.size()==0) break;
		auto it = st.upper_bound(s-cur);
		if(it==st.begin()) continue;
		st.erase(prev(it));
	}
	return r<=ride;
}
ll f(ll ride){
	ll l = 0;
	ll r = INT32_MAX;
	while(l<=r){
		ll mid = (l+r)>>1;
		if(!pos(mid,ride)) l = mid+1;
		else r = mid-1;
	}
	return ride*l;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	map<int,int>m;
	for(int i=1; i<=n; i++){
		int a; cin>>a;
		m[a]++;
	}
	for(auto p : m) arr.push_back(p.second);
	sort(arr.begin(),arr.end());
	if(arr.size()==1){
		cout<<arr.back();
		return 0;
	}
	ll ans = INT64_MAX;
	for(int i=(arr.size()/2+arr.size()%2); i<=arr.size(); i++){
		ans = min(ans,f(i));
	}
	cout<<ans;
}

https://codeforces.com/problemset/problem/1250/B

this problem has no editorial. i just iterated all possible r and calculate minimum s with binary search

doing binary search, i greedily tried to take two teams at one ride if it's possible. if s is fixed and current team has c member, i checked whether there's a team with maximum number of members d <= (s-c) if there's such team, two team can ride together, otherwise just take one time at this ride.

is it logically wrong? or implementation is wrong? need help! (also i wanna know if there's a solution with complexity k^2 or faster , since my code is too slow )

UDP: another version that doesn't use binary search and multiset yet produces same Wrong Answer.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
vector<int>arr;
int pointer;
 
bool pos(ll s,ll ride){
	if(s<arr.back()) return 0;
	deque<int>deq(arr.begin(),arr.end());
	ll ret = 0;
	while(deq.size()){
		ret++;
		int sz = deq.back();
		deq.pop_back();
		if(deq.size() && deq.front()+sz<=s){
			deq.pop_front();
		}
	}
	return ret<=ride;
}
ll f(ll ride){
	while(pos(pointer,ride)) pointer--;
	pointer++;
	return ride*pointer;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	map<int,int>m;
	for(int i=1; i<=n; i++){
		int a; cin>>a;
		m[a]++;
	}
	for(auto p : m) arr.push_back(p.second);
	sort(arr.begin(),arr.end());
	if(arr.size()==1){
		cout<<arr.back();
		return 0;
	}
 
	pointer = n;
	ll ans = INT64_MAX;
	for(int i=(arr.size()/2+arr.size()%2); i<=arr.size(); i++){
		ans = min(ans,f(i));
	}
	cout<<ans;
}