QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369852 | #8216. Jumbled Primes | ucup-team3215 | AC ✓ | 442ms | 3540kb | C++20 | 2.4kb | 2024-03-28 18:42:41 | 2024-03-28 18:42:42 |
Judging History
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