Niloy007

Prime Cuts || UVA

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 middle(int n) {
  35.     return n / 2;
  36. }
  37.  
  38. void handleEven(int c, int mid) {
  39.     int count = 0;
  40.     int index = mid;
  41.     output.push_back(Prime[mid]);
  42.     while(true) {
  43.         if(count == c - 1) {
  44.             break;
  45.         }
  46.         output.push_back(Prime[++index]);
  47.         count++;
  48.     }
  49.     count = 0;
  50.     index = mid;
  51.     while(true) {
  52.         if(count == c) {
  53.             break;
  54.         }
  55.         output.push_back(Prime[--index]);
  56.         count++;
  57.     }
  58. }
  59.  
  60. void handleOdd(int c, int mid) {
  61.     int count = 0;
  62.     int index = mid;
  63.     output.push_back(Prime[mid]);
  64.     while(true) {
  65.         if(count == c - 1) {
  66.             break;
  67.         }
  68.         output.push_back(Prime[++index]);
  69.         count++;
  70.     }
  71.     count = 0;
  72.     index = mid;
  73.     while(true) {
  74.         if(count == c - 1) {
  75.             break;
  76.         }
  77.         output.push_back(Prime[--index]);
  78.         count++;
  79.     }
  80. }
  81.  
  82. void print(int n, int c) {
  83.     cout << n << " " << c << ":";
  84.     if(n == 1) {
  85.         cout << " " << 1 << endl;
  86.     } else {
  87.         for (int i : output) {
  88.             if(i < Prime[n])
  89.                 cout << " " << i;
  90.         }
  91.         cout << endl;
  92.     }
  93. }
  94.  
  95.  
  96. int main() {
  97. #ifndef Niloy
  98.     freopen("input.txt", "r", stdin);
  99.     freopen("output.txt", "w", stdout);
  100. #endif
  101.     ios_base::sync_with_stdio(false);
  102.     cin.tie(NULL);
  103.  
  104.     sieve();
  105.     for (int i = 0; i <= max; i++) {
  106.         if(isPrime[i] == 1) {
  107.             Prime.push_back(i);
  108.         }
  109.     }
  110.  
  111.     int n, c, length;
  112.  
  113.     while(cin >> n >> c) {
  114.         output.clear();
  115.         length = 0;
  116.         for (int i = 0; i < n; i++) {
  117.             if(Prime[i] <= n) {
  118.                 length++;
  119.             }
  120.         }
  121.         int mid = middle(length);
  122.         if(n == 1) {
  123.             print(n, c);
  124.         } else {
  125.             if(length < c) {
  126.                 for (int i = 0; i < length; i++) {
  127.                     output.push_back(Prime[i]);
  128.                 }
  129.             } else if(length % 2 == 0) {
  130.                 handleEven(c, mid);
  131.             } else {
  132.                 handleOdd(c, mid);
  133.             }
  134.             sort(output.begin(), output.end());
  135.             print(n, c);
  136.         }
  137.         cout << endl;
  138.         output.clear();
  139.     }
  140.  
  141.     return 0;
  142. }
RAW Paste Data