Niloy007

Prime Cuts || UVA Solution

May 12th, 2020
107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define max 9000
  3. #define pb push_back
  4. #define pairs pair<int, int>
  5. #define vi vector<int>
  6. #define vb vector<bool>
  7. #define vii vector<pairs>
  8. #define lb lower_bound
  9. #define ub upper_bound
  10. #define lli long long int
  11. #define endl '\n'
  12. using namespace std;
  13.  
  14. bool isPrime[max];
  15. vi Prime;
  16. vi output;
  17.  
  18. void sieve() {
  19.     memset(isPrime, true, sizeof(isPrime));     // first all odd number's prime
  20.  
  21.     isPrime[0] = 0;
  22.  
  23.     // Sieve
  24.     for (int i = 2; i * i <= max; i++) {
  25.         if(isPrime[i]) {
  26.             for (int j = i * i; j <= max; j += i) {
  27.                 isPrime[j] = 0;
  28.             }
  29.         }
  30.     }
  31. }
  32.  
  33.  
  34. int main() {
  35. #ifndef Niloy
  36.     freopen("input.txt", "r", stdin);
  37.     freopen("output.txt", "w", stdout);
  38. #endif
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(NULL);
  41.  
  42.     sieve();
  43.     for (int i = 0; i <= max; i++) {
  44.         if(isPrime[i] == 1) {
  45.             Prime.push_back(i);
  46.         }
  47.     }
  48.  
  49.     int n, c, length;
  50.  
  51.     while(cin >> n >> c) {
  52.         output.clear();
  53.         length = 0;
  54.         cout << n << " " << c << ":";
  55.         for (int i = 0; i < n; i++) {
  56.             if(Prime[i] <= n) {
  57.                 output.push_back(Prime[i]);
  58.                 length++;
  59.             }
  60.         }
  61.         int mid = middle(length);
  62.  
  63.         mid += 1;
  64.         cout << mid << " " << length << endl;
  65.         if(length < 2 * c) {
  66.             for (int i = 0; i < output.size(); i++) {
  67.                 cout << " " <<  output[i];
  68.             }
  69.         } else if(length % 2 == 0) {
  70.             int b = c - 1;
  71.             cout << b << endl;
  72.             int low = mid - b;
  73.             int high = mid + c;
  74.             cout << low << " " << high << endl;
  75.             for (int i = low - 2; i < high - 1; i++) {
  76.                 cout << " " << output[i];
  77.             }
  78.         } else {
  79.             int b = c - 1;
  80.             int low = mid - b;
  81.             int high = mid + b;
  82.             for (int i = low - 1; i < high; i++)
  83.                 cout << " " << output[i];
  84.         }
  85.  
  86.         cout << endl << endl;
  87.     }
  88.  
  89.     return 0;
  90. }
RAW Paste Data