QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#335100 | #8216. Jumbled Primes | ucup-team1209# | AC ✓ | 757ms | 3668kb | C++20 | 4.1kb | 2024-02-22 17:24:35 | 2024-02-22 17:24:36 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 105;
int n = 100;
int cnt;
struct mm {
private:
int p[N];
int is[N];
int baseqry(int a, int b) {
std::cout << "? " << a << ' ' << b << '\n';
int res; cin >> res;
return res;
assert(a != b);
++ cnt;
return std::gcd(p[a], p[b]);
}
std::map<int, int> map;
public:
int qry(int a, int b) {
if(a > b) std::swap(a, b);
int z = a * n + b;
auto iter = map.find(z);
if(iter != map.end()) return iter -> second;
return map[z] = baseqry(a, b);
}
void submit(int * ans) {
cout << "! ";
for(int i = 1;i <= n;++i) {
cout << ans[i];
}
cout << '\n';
return ;
for(int i = 1;i <= n;++i) {
if(ans[i] != is[p[i]]) {
assert(ans[i] == is[p[i]]);
}
}
}
void init() {
static std::mt19937 gen(20);
map.clear();
for(int i = 1;i <= n;++i) p[i] = i, is[i] = 1;
for(int i = 2;i <= n;++i)
for(int j = i + i;j <= n;j += i) is[j] = 0;
std::shuffle(p + 1, p + n + 1, gen);
std::shuffle(p + 1, p + n + 1, gen);
std::shuffle(p + 1, p + n + 1, gen);
}
} q;
int ans[N];
int main() {
std::mt19937_64 gen(1);
std::ios::sync_with_stdio(false);
for(int i = 1;i <= 1000;++i) {
q.init();
int v[4] = {-1, -1, -1, -1};
for(;v[1] == -1 || v[2] == -1 || v[3] == -1;) {
int a = gen() % n + 1, b;
do b = gen() % n + 1; while(a == b);
int res = q.qry(a, b);
if(res % 5 == 0) v[1] = a;
if(res % 7 == 0) v[2] = a;
if(res % 4 == 0) v[3] = a;
}
std::vector<int> p5 = {v[1]};
std::vector<int> p7 = {v[2]};
auto ins = [&](auto & v, int i, int p, int nd) {
if(i == v[0]) return -1;
int z = q.qry(v[0], i);
if(z % p) return -1;
if(z % nd == 0) return v[0];
for(int j = 1;j < (int) v.size();++j) {
if(q.qry(v[j], i) % nd == 0) return i;
}
v.push_back(i);
return -1;
};
int v35 = -1;
int v27 = -1;
for(int i = 1;i <= n;++i) {
if(v35 < 0) {
int p = ins(p5, i, 5, 3);
if(p > 0) v35 = p;
}
if(v27 < 0) {
int p = ins(p7, i, 7, 2);
if(p > 0) v27 = p;
}
}
std::vector<int> vc[1 << 4];
for(int i = 1;i <= n;++i) {
int mask = 0;
if(v27 == i) mask |= 9;
else {
int w = q.qry(v27, i);
if(w % 2 == 0) mask |= 1;
if(w % 7 == 0) mask |= 8;
}
if(v35 == i) mask |= 6;
else {
int w = q.qry(v35, i);
if(w % 3 == 0) mask |= 2;
if(w % 5 == 0) mask |= 4;
}
ans[i] = mask == 0;
vc[mask].push_back(i);
}
auto solve0 = [&](std::vector<int> & v, std::vector<int> & pms, int pb = 1) {
std::vector<int> res;
for(int i : v) {
int ok = 1;
for(int id = 0;id < (int) pms.size();++id) {
int & j = pms[id];
if((pb || j > 0) && q.qry(i, std::abs(j)) > 1) {
if(j > 0) j *= -1;
ok = 0;
break;
}
}
if(ok) res.push_back(i);
}
v = res;
};
auto solve1 = [&](std::vector<int> & v, int p) {
for(int j = 0;j < (int) v.size();++j) {
int ok = 1;
for(int k : v) {
if(v[j] == k) continue;
if(q.qry(v[j], k) != p) {
ok = 0;
break;
}
}
if(ok) {
ans[v[j]] = 1;
break;
}
}
};
auto solve2 = [&](std::vector<int> & v, int p) {
int mk = 1 | (p == 5 ? 4 : 8);
int yes = 1, pb = v[0];
for(int j : vc[mk]) {
int ans = q.qry(pb, j);
if(ans > p) {
yes = 0;
break;
}
}
ans[yes ? v[0] : v[1]] = 1;
};
vc[1].erase(remove_if(vc[1].begin(), vc[1].end(), [&](int x) {
return x == v[3] || q.qry(x, v[3]) % 4 == 0;
}), vc[1].end());
solve0(vc[1], vc[0], 0);
std::vector<int> p;
for(int x : vc[0]) if(x < 0) p.push_back(-x);
vc[0] = p;
solve0(vc[2], vc[0]), p = {};
for(int x : vc[0]) if(x < 0) p.push_back(-x);
vc[0] = p;
solve0(vc[4], vc[0]), p = {};
for(int x : vc[0]) if(x < 0) p.push_back(-x);
vc[0] = p;
solve0(vc[8], vc[0]), p = {};
for(int x : vc[0]) if(x < 0) p.push_back(-x);
vc[0] = p;
solve1(vc[1], 2);
solve1(vc[2], 3);
solve2(vc[4], 5);
solve2(vc[8], 7);
q.submit(ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 757ms
memory: 3668kb
input:
1 3 1 1 2 2 1 1 2 3 1 1 1 1 3 1 1 3 1 1 1 2 1 2 1 13 1 2 1 2 2 1 1 1 1 6 1 1 1 4 25 4 1 1 2 1 1 3 6 1 1 1 1 1 1 2 1 1 2 4 1 5 1 1 1 1 1 1 1 1 1 3 1 3 1 3 1 9 7 1 1 1 7 1 1 25 5 1 1 2 1 50 25 5 1 1 1 1 5 5 5 5 2 1 4 1 10 5 10 5 5 1 1 2 7 7 1 1 4 1 5 4 1 4 1 20 5 10 5 30 5 1 1 5 1 1 1 1 1 1 1 5 1 1 5 ...
output:
? 29 63 ? 31 47 ? 10 85 ? 29 66 ? 25 49 ? 64 77 ? 8 78 ? 34 81 ? 11 70 ? 1 24 ? 68 84 ? 68 89 ? 28 95 ? 40 78 ? 1 31 ? 4 66 ? 29 38 ? 5 47 ? 55 92 ? 21 30 ? 29 85 ? 25 58 ? 27 100 ? 20 100 ? 23 91 ? 32 89 ? 18 33 ? 15 48 ? 36 52 ? 58 59 ? 12 88 ? 9 49 ? 14 100 ? 60 90 ? 11 23 ? 53 93 ? 36 75 ? 40 60...
result:
ok Primes are found successfully with S = 577423 queries total