fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fix(f,n) std::fixed<<std::setprecision(n)<<f
  4. #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. typedef long long int ll;
  6. typedef unsigned long long int ull;
  7. #define vi vector<int>
  8. #define pii pair<int,int>
  9. #define vii vector<pii>
  10. #define max(a,b) ((a>b)?a:b)
  11. #define min(a,b) ((a>b)?b:a)
  12. #define max3(a,b,c) ((a>b)?(a>c)?a:c:(b>c)?b:c)
  13. #define min3(a,b,c) ((a<b)?(a<c)?a:c:(b<c)?b:c)
  14. #define REP(i,a,n) for(ll i=a;i<n;i++)
  15. #define pb push_back
  16. #define mp make_pair
  17.  
  18. ll arr[100000];
  19. ll n,p;
  20.  
  21. ll bs(ll key){
  22. ll l=0, r=(n-1),mid,ans=0;
  23. while(l<=r){
  24. mid=(l+r)/2;
  25. if(arr[mid]==key){
  26. mid++;
  27. while(mid<n && arr[mid]==key){
  28. mid++;
  29. }
  30. return mid;
  31. }else if(arr[mid]>key){
  32. r=mid-1;
  33. }else{
  34. ans=mid+1;
  35. l=mid+1;
  36. }
  37. }
  38. return ans;
  39. }
  40.  
  41. bool check(ll x){
  42. if(bs(x)<p){
  43. return 1;
  44. }
  45. return 0;
  46. }
  47.  
  48. int main(){
  49. fast;
  50. int test=1;
  51. //cin >> test;
  52. while(test--){
  53. cin >> n >> p;
  54. ll minv=1000000001,maxv=-1;
  55. for(ll i=0 ; i<n ; i++){
  56. cin >> arr[i];
  57. maxv=max(maxv,arr[i]);
  58. minv=min(minv,arr[i]);
  59. }
  60. sort(arr,arr+n);
  61. ll sum=0,temp=minv;
  62. for(int i=1 ; i<n ; i++){
  63. sum+=(arr[i]-arr[i-1]-1);
  64. temp=max(temp,minv+sum);
  65. }
  66. minv=temp;
  67. ll ans=-1;
  68. ll l=minv,r=maxv,mid;
  69. while(l<=r){
  70. mid=(l+r)/2;
  71. if(!check(mid)){
  72. r=mid-1;
  73. }else{
  74. l=mid+1;
  75. ans=mid;
  76. }
  77. }
  78. if(ans==-1){
  79. cout << 0 << endl;
  80. return 0;
  81. }
  82. cout << ans-minv+1 << endl;
  83. for(ll i=minv ; i<=ans ; i++){
  84. cout << i << " ";
  85. }
  86. }
  87. return 0;
  88. }
Success #stdin #stdout 0s 4396KB
stdin
Standard input is empty
stdout
0