fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/iUJnps
language:
C++14 (gcc 8.3)
created:
3 years 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!