fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. ll count_smaller_elements(vector<int> &nums, vector<pair<int, int>> &diffs, ll x, ll k)
  6. {
  7. 	ll cnt=0;
  8.  
  9. 	for(ll i=1; i<nums.size()-1; i++)
  10. 	{	
  11. 		int minm, maxm;
  12. 		minm = diffs[i-1].first;
  13. 		maxm = diffs[i-1].second;
  14. 		if(maxm<=x)
  15. 		{	
  16. 			cnt+=(nums.size()-i);
  17. 			if(cnt>=k) return cnt;
  18. 		}
  19. 		else
  20. 		{	
  21. 			for(ll j=0; j<nums.size()-i; j++)
  22. 			{
  23. 				if(abs(nums[j]-nums[j+i])<=x) cnt++;
  24. 				if(cnt>=k) return cnt;
  25. 			}
  26. 		}
  27. 	}
  28. 	return cnt;
  29. }
  30.  
  31. ll find_kth_smallest(vector<int> &nums, vector<pair<int, int>> &diffs, ll k, ll left, ll right)
  32. {
  33. 	if(left>right) return -1;
  34.  
  35. 	ll mid = (left+right)/2;
  36.  
  37. 	if(count_smaller_elements(nums, diffs, mid, k)>=k)
  38. 	{
  39. 		ll next = find_kth_smallest(nums, diffs, k, left, mid-1);
  40. 		if(next==-1) return mid;
  41. 		return next;
  42. 	}
  43. 	return find_kth_smallest(nums, diffs, k, mid+1, right);
  44. }
  45.  
  46. int main() {
  47.     // your code goes here
  48. 	ll n, p;
  49. 	cin>>n;
  50. 	vector<int> nums(n);
  51. 	for(int i=0; i<n; i++)
  52. 	{
  53. 		cin>>nums[i];
  54. 	}
  55. 	sort(nums.begin(), nums.end());
  56. 	vector<pair<int, int>> diffs(n);
  57. 	for(ll i=1; i<nums.size()-1; i++)
  58. 	{	
  59. 		int minm=INT_MAX, maxm=INT_MIN;
  60. 		for(ll j=0; j<nums.size()-i; j++)
  61. 		{
  62. 			int d=(abs(nums[j]-nums[j+i]));
  63. 			minm = min(minm, d);
  64. 			maxm = max(maxm, d);
  65. 		}
  66. 		diffs[i-1]={minm, maxm};
  67. 	}
  68. 	ll k;
  69. 	cin>>k;
  70. 	cout<<"test"<<endl;
  71. 	cout<<find_kth_smallest(nums, diffs, k, 0, nums.back()-nums.front());
  72.     return 0;
  73. }
Success #stdin #stdout 0.01s 5568KB
comments (?)
stdin
copy 
3
1 3 1
1
stdout
copy 
test
0
https://ideone.com/gosBFS
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!