fork(21) download
copy 
  1.     #include <algorithm>
  2.     #include <bitset>
  3.     #include <cassert>
  4.     #include <cctype>
  5.     #include <cmath>
  6.     #include <cstdio>
  7.     #include <cstdlib>
  8.     #include <cstring>
  9.     #include <ctime>
  10.     #include <deque>
  11.     #include <functional>
  12.     #include <iomanip>
  13.     #include <iostream>
  14.     #include <limits>
  15.     #include <list>
  16.     #include <map>
  17.     #include <numeric>
  18.     #include <queue>
  19.     #include <set>
  20.     #include <sstream>
  21.     #include <stack>
  22.     #include <string>
  23.     #include <utility>
  24.     #include <vector>
  25.  
  26.     using namespace std;
  27.  
  28.     #ifndef ONLINE_JUDGE
  29.     	bool debug = false;
  30.     #else
  31.     	bool debug = true;
  32.     #endif
  33.  
  34.     typedef vector <int> vi;
  35.     typedef pair <int, int> pii;
  36.  
  37.     //definition
  38.     #define gc() getchar()
  39.     #define pc() putchar()
  40.  
  41.     #define MOD 1000000007
  42.     #define MAX 100005
  43.     #define pi 3.14159265358979
  44.     #define ESP (1e-9)
  45.  
  46.     #define llu long long unsigned
  47.     #define lld long long
  48.     #define ld long
  49.  
  50.     #define fu(i,a,n) for(i=a;i<n;i++)
  51.     #define fue(i,a,n) for(i=a;i<=n;i++)
  52.     #define fd(i,n,a) for(i=n;i>a;i--)
  53.     #define fde(i,n,a) for(i=n;i>=a;i--)
  54.     #define fr(i,a) for(i=0;i<a;i++)
  55.     #define fe(i,a) for(i=0;i<=a;i++)
  56.  
  57.     #define sf_d(n) scanf("%d",&n)
  58.     #define sf_ld(n) scanf("%ld",&n)
  59.     #define sf_lld(n) scanf("%lld",&n)
  60.  
  61.     #define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  62.     #define all(vi) vi.begin(), vi.end()
  63.     #define len length()
  64.     #define pb push_back
  65.     #define sz size()
  66.     #define mp make_pair
  67.     #define clr clear()
  68.     #define ff first
  69.     #define ss second
  70.     #define imax numeric_limits<int>::max()
  71.     #define imin numeric_limits<int>::min()
  72.     #define ldmax numeric_limits<ld>::max()
  73.     #define ldmin numeric_limits<ld>::min()
  74.     #define lldmax numeric_limits<lld>::max()
  75.     #define lldmin numeric_limits<lld>::min()
  76.     //end of definition
  77.  
  78.     //fast input
  79.  
  80.     int scan_d()	{register int c=gc();int x=0;for(;(c<48 || c>57);c = gc());for(;c>47 && c<58;c = gc()){x = (x<<1) + (x<<3) + c - 48;}return x;}
  81.     ld scan_ld()    {int ip=getchar(),flag=1;ld ret=0;for(;ip<'0'||ip>'9';ip=getchar())if(ip=='-'){flag=-1;ip=getchar();break;}for(;ip>='0'&&ip<='9';ip=getchar())ret=ret*10+ip-'0';return flag*ret;}
  82.     lld scan_lld()    {int ip=getchar(),flag=1;lld ret=0;for(;ip<'0'||ip>'9';ip=getchar())if(ip=='-'){flag=-1;ip=getchar();break;}for(;ip>='0'&&ip<='9';ip=getchar())ret=ret*10+ip-'0';return flag*ret;}
  83.     llu scan_llu()    {int ip=getchar();llu ret=0;for(;ip<'0'||ip>'9';ip=getchar());for(;ip>='0'&&ip<='9';ip=getchar())ret=ret*10+ip-'0';return ret;}
  84.  
  85.     //end of fast input
  86.  
  87.     //fast output
  88.  
  89.     //no line break
  90.     void print_d(int n)     {if(n<0){n=-n;putchar('-');}int i=10;char output_buffer[10];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<10);}
  91.     void print_ld(ld n)     {if(n<0){n=-n;putchar('-');}int i=11;char output_buffer[11];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<11);}
  92.     void print_lld(lld n)     {if(n<0){n=-n;putchar('-');}int i=21;char output_buffer[21];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<21);}
  93.     void print_llu(llu n)     {int i=21;char output_buffer[21];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<21);}
  94.  
  95.     //new line
  96.     void println_d(int n)     {if(n<0){n=-n;putchar('-');}int i=10;char output_buffer[11];output_buffer[10]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<11);}
  97.     void println_ld(ld n)     {if(n<0){n=-n;putchar('-');}int i=11;char output_buffer[12];output_buffer[11]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<12);}
  98.     void println_lld(lld n)     {if(n<0){n=-n;putchar('-');}int i=21;char output_buffer[22];output_buffer[21]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  99.     void println_llu(llu n)     {int i=21;char output_buffer[22];output_buffer[21]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  100.  
  101.     //special char
  102.     char sp;
  103.     void printsp_d(int n)     {if(n<0){n=-n;putchar('-');}int i=10;char output_buffer[11];output_buffer[10]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<11);}
  104.     void printsp_ld(ld n)     {if(n<0){n=-n;putchar('-');}int i=11;char output_buffer[12];output_buffer[11]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<12);}
  105.     void printsp_lld(lld n)     {if(n<0){n=-n;putchar('-');}int i=21;char output_buffer[22];output_buffer[21]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  106.     void printsp_llu(llu n)     {int i=21;char output_buffer[22];output_buffer[21]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  107.  
  108.     //end of fast output
  109.  
  110.  
  111.     int ar[100001],n,c;
  112.  
  113.  
  114.     int fnc(int x)
  115.     {
  116.     	int i,temp;
  117.     	temp=1;
  118.     	lld prev;
  119.     	prev=ar[0];
  120.     	fu(i,1,n)
  121.     	{
  122.     		if(ar[i]-prev>=x)
  123.     		{
  124.     			temp++;
  125.     			if(temp==c)
  126.     				return 1;
  127.     			prev=ar[i];
  128.     		}
  129.     	}
  130.     	return 0;
  131.     }
  132.  
  133.  
  134.     void binsearch()
  135.     {
  136.     	int l,r,mid;
  137.     	l=0;
  138.     	r=ar[n-1];
  139.     	while(l<r)
  140.     	{
  141.     		mid=(l+r)/2;
  142.     		if(fnc(mid)==1)
  143.     			l=mid+1;
  144.     		else
  145.     			r=mid;
  146.     	}
  147.     	println_lld(l-1);
  148.     }
  149.  
  150.     int main()
  151.     {
  152.     /*	freopen("input.txt", "r", stdin);
  153.     	freopen("output.txt", "w", stdout);*/
  154.     	lld t,i;
  155.     	t=scan_lld();
  156.     	while(t--)
  157.     	{
  158.     		n=scan_d();
  159.     		c=scan_d();
  160.     		fr(i,n)
  161.     			ar[i]=scan_d();
  162.     		sort(ar,ar+n);
  163.     		binsearch();
  164.     	}
  165.     	return 0;
  166.     }
Success #stdin #stdout 0s 3860KB
comments (?)
stdin
copy 
1
5 3
1
2
8
4
9
stdout
copy 
3
https://ideone.com/EMdzlP
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!