QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369852#8216. Jumbled Primesucup-team3215AC ✓442ms3540kbC++202.4kb2024-03-28 18:42:412024-03-28 18:42:42

Judging History

你现在查看的是最新测评结果

  • [2024-03-28 18:42:42]
  • 评测
  • 测评结果:AC
  • 用时:442ms
  • 内存:3540kb
  • [2024-03-28 18:42:41]
  • 提交

answer

#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>

using namespace std;

constexpr int N = 100;

int ask(int i, int j) {
  cout << "? " << i + 1 << ' ' << j + 1 << '\n';
  int g; cin >> g;
  return g;
}

int g[N];

int solve() {
  int que = 0;
  mt19937_64 rng;
  int piv[4]{4, 3, 5, 7};
  int hv = 0, ex[16], gpiv[16]{1};
  for (int i = 1; i < 16; ++i) ex[i] = -1, gpiv[i] = lcm(gpiv[i & i - 1], piv[__builtin_ctz(i)]);
  int ord[N], pos = N;
  for (int i = 0; i < N; ++i) ord[i] = i;
  while (hv != 15) {
    if (pos == N) shuffle(ord, ord + N, rng), pos = 0;
    int a = ord[pos++], b = ord[pos++], g = ask(a, b); ++que;
    int cur = 0;
    for (int i = 0; i < 4; ++i) if (g % piv[i] == 0) hv |= cur |= 1 << i;
    for (int t = cur; t; --t &= cur) ex[t] = a;
  }
  auto sask = [&](int i, int a) { return i != ex[a]? ++que, ask(i, ex[a]): gpiv[a]; };
  for (int i = 0, done = 1; done--, i < N; ++i) {
    for (int a = 1; !done && a < 16; ++a) if (int b = 15 - a; done = ~ex[a] && ~ex[15 - a]) g[i] = lcm(sask(i, a), sask(i, b));
    for (int a = 1; !done && a < 16; ++a) if (int b = 15 - a & a - 15; done = (a & a - 1) && ~ex[a]) g[i] = lcm(sask(i, a), lcm(sask(i, b), sask(i, 15 - a - b)));
    if (!done) g[i] = lcm(lcm(sask(i, 1), sask(i, 2)), lcm(sask(i, 4), sask(i, 8))), done = 1;
    g[i] = gcd(g[i], gpiv[15]);
    int cur = 0;
    for (int j = 0; j < 4; ++j) if (g[i] % piv[j] == 0) hv |= 1 << j, cur |= 1 << j;
    for (int t = cur; t; --t &= cur) ex[t] = i;
  }
  auto match = [&](int ga, int gb, int lmf, int lms) {
    int s = 0;
    for (int a = 0; a < 100; ++a) if (g[a] == ga) {
      int f = 0;
      for (int b = 0; b < 100 && f < lmf; ++b) if (g[b] == gb) {
        int gg = ask(a, b); ++que;
        if (gg == gcd(ga, gb)) { ++f; continue; }
        g[a] = lcm(g[a], gg), g[b] = lcm(g[b], gg);
        if (lmf == 99) break;
      }
      if ((s += g[a] != ga) == lms) break;
    }
  };
  match(14, 7, 99, 1);
  match(10, 5, 99, 1);
  match(30, 3, 9, 1);
  match(7, 5, 99, 2);
  match(3, 2, 99, 7);
  match(2, 1, 99, 4);
  match(34, 5, 99, 1);
  match(38, 5, 99, 1);
  string s(N, '0');
  for (int i = 0; i < N; ++i) s[i] += g[i] == 2 || g[i] == 3 || g[i] == 5 || g[i] == 7 || gcd(g[i], gpiv[15]) == 1;
  cout << "! " << s << '\n';
  return que;
}

int main() {
  int s = 0;
  for (int i = 0; i < 1000; ++i) {
    s += solve();
  }
  assert(s < 420000);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 442ms
memory: 3540kb

input:

1
1
1
2
1
1
3
1
1
1
3
2
3
2
1
1
1
1
1
1
3
2
1
1
1
12
1
4
3
1
17
1
1
1
1
1
1
1
1
3
2
1
1
1
3
2
1
1
1
1
1
2
2
1
1
2
6
2
2
2
2
2
4
1
5
1
1
1
4
3
3
1
1
1
1
1
1
11
2
2
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
1
3
3
49
1
1
3
7
1
1
1
1
1
1
5
1
1
1
9
1
1
2
1
25
2
11
1
1
1
1
1
1
5
1
1
1
2
1
1
4
1
5
18
11
3
3
7
2
2
1
...

output:

? 15 50
? 89 79
? 59 52
? 19 85
? 68 41
? 51 8
? 56 91
? 35 29
? 63 12
? 32 77
? 38 24
? 6 73
? 36 13
? 94 37
? 97 11
? 9 71
? 22 66
? 42 99
? 4 53
? 2 75
? 81 27
? 26 57
? 46 60
? 5 80
? 23 58
? 65 21
? 16 55
? 20 49
? 33 83
? 95 39
? 40 25
? 34 43
? 86 69
? 84 90
? 44 67
? 76 47
? 3 70
? 82 7
? 92...

result:

ok Primes are found successfully with S = 416964 queries total