cmimc

Code for the 2021 CMIMC Programming Contest

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

bool comp[200005];

//#define BOUND 40

void find_all(int m, int min_factor, int max_factor, vector<int>& res)
{
    for (int i = 2; i <= m; i++) {
        int cur = i;
        bool good = true;
        for (int j = 2; j * j <= i; j++) {
            while (cur % j == 0) {
                cur /= j;
                if (j < min_factor || j > max_factor) good = false;
            }
        }
        if (cur < min_factor || cur > max_factor) good = false;
        if (good) res.push_back(i);
    }
}

int solve_bound(int n, int m)
{
    int BOUND;
    if (m == 40000) {
        BOUND = 46;
    } else if (m == 4000) {
        BOUND = 20;
    } else {
        BOUND = 10;
    }
    vector<int> group1, group2;
    find_all(m, 1, BOUND, group1);
    find_all(m, BOUND + 1, m, group2);
    fprintf(stderr, "%d %d\n", (int)group1.size(), (int)group2.size());
    for (int i = 0; i < min(group1.size(), group2.size()); i++) {
        printf("%d ", group1[i]);
    }
    printf("\n");
    for (int i = 0; i < min(group1.size(), group2.size()); i++) {
        printf("%d ", group2[i]);
    }
}

int main()
{
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 2; i <= 200000; i++) {
       if (comp[i]) continue;
       for (int j = i * 2; j <= 200000; j += i) {
           comp[j] = true;
       }
    }
    if (n == 2) {
        solve_bound(n, m);
    } else {
        vector<int> primes;
        int prime_above_cnt = 0;
        for (int i = 2; i <= m; i++) {
            if (!comp[i]) {
                primes.push_back(i);
            }
        }
        printf("%d\n", prime_above_cnt);
        int cnt = primes.size() / n;
        for (int i = 0; i < n; i++) {
            for (int j = i * cnt; j < (i + 1) * cnt; j++) {
                printf("%d ", primes[j]);
            }
            printf("\n");
        }
    }
    return 0;
}