QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#350326 | #8216. Jumbled Primes | ucup-team1198# | AC ✓ | 853ms | 3880kb | C++20 | 6.0kb | 2024-03-10 17:16:51 | 2024-03-10 17:16:51 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int ask_count = 0;
vector<int> ans_p;
int gcd(int x, int y) {
if (x == 0) return y;
return gcd(y % x, x);
}
map<pair<int, int>, int> mem;
int ask(int p1, int p2) {
// mem?
if (mem.count({p1, p2})) return mem[{p1, p2}];
if (mem.count({p2, p1})) return mem[{p2, p1}];
++ask_count;
// mem[{p1, p2}] = gcd(ans_p[p1], ans_p[p2]);
// return gcd(ans_p[p1], ans_p[p2]);
cout << "? " << p1 + 1 << ' ' << p2 + 1 << endl;
int res;
cin >> res;
mem[{p1, p2}] = res;
return res;
}
string answer;
bool prime(int x) {
// if (x == 1) return 1;
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) return 0;
}
return 1;
}
void check() {
for (int i = 0; i < 100; ++i) {
if (answer[i] - '0' != prime(ans_p[i])) {
cerr << "wrong! " << i + 1 << '\n';
assert(0);
}
}
}
vector<vector<int>> sep(vector<int> ind, int with, vector<int> by, int mark = 0) {
vector<vector<int>> res(by.size() + 1);
for (int i : ind) {
if (i == with) {
if (mark >= 1) {
answer[i] = '0';
}
res[0].push_back(i);
continue;
}
int a = ask(i, with);
for (int j = 0; j <= by.size(); ++j) {
if (j == by.size() || gcd(a, by[j]) % by[j] == 0) {
if (j < mark) {
// cerr << "mark " << i + 1 << '\n';
answer[i] = '0';
}
res[j].push_back(i);
break;
}
}
}
return res;
}
int fnd(vector<int> ind, int by) {
int p1 = -1;
int p2 = -1;
while (true) {
p1 = ind[rand() % ind.size()];
p2 = p1;
while (p2 == p1) p2 = ind[rand() % ind.size()];
if (ask(p1, p2) % by == 0) break;
}
return p1; // forget p2
}
vector<pair<int, int>> big_primes(vector<int> ind, vector<int> indp) {
vector<pair<int, int>> res;
for (int i : indp) {
for (int j = 0; j < ind.size(); ++j) {
int a = ask(i, ind[j]);
if (a != 1) {
res.push_back({i, a});
answer[ind[j]] = '0';
ind.erase(ind.begin() + j);
break;
}
}
}
return res; // ind, val
}
void filter(vector<int> ind, int d, vector<pair<int, int>> bp) {
for (auto p : bp) {
if (p.second * d > 100) continue;
for (int i = 0; i < ind.size(); ++i) {
int a = ask(ind[i], p.first);
if (a != 1) {
answer[ind[i]] = '0';
ind.erase(ind.begin() + i);
break;
}
}
}
}
void find_p2(vector<int> ind, vector<int> with, int g) {
bool checked = false;
for (int i : ind) {
if (answer[i] == '0') continue;
if (checked) {
answer[i] = '0';
break;
}
for (int j : with) {
if (ask(i, j) % g == 0) {
checked = true;
break;
}
}
if (checked) {
answer[i] = '0';
break;
}
checked = true;
}
}
void print(vector<int> v, string name = "vec") {
cerr << name << " = ";
for (int i : v) {
cerr << i + 1 << ' ';
}
cerr << '\n';
}
void print(vector<vector<int>> v, string name = "vec") {
cerr << name << " = ";
for (auto vv : v) {
for (auto i : vv) {
cerr << i + 1 << ' ';
}
cerr << '\n';
}
cerr << '\n';
}
void solve() {
int n = 100;
answer.assign(n, '1');
vector<int> ind(n);
iota(ind.begin(), ind.end(), 0);
// rsh
int d4 = fnd(ind, 4);
vector<vector<int>> d421 = sep(ind, d4, {4, 2}, 1);
// print(d421, "d421");
int d9 = fnd(d421[2], 9);
vector<vector<int>> d931 = sep(d421[2], d9, {9, 3}, 1);
// print(d931, "d931");
int d5 = fnd(d931[2], 5);
vector<vector<int>> d51 = sep(d931[2], d5, {5});
// print(d51, "d51");
int d7 = fnd(d51[1], 7);
vector<vector<int>> d71 = sep(d51[1], d7, {7});
// print(d51, "d71");
vector<int> p1_11 = d71[1];
vector<vector<int>> c_35_ost = sep(d51[0], d71[0][0], {7}, 1);
vector<vector<int>> c_3_57_ost = sep(d931[1], c_35_ost[0][0], {5, 7}, 2);
vector<vector<int>> c_2_57_ost = sep(d421[1], c_35_ost[0][0], {5, 7}, 2);
vector<vector<int>> c_2_357_ost = sep(c_2_57_ost[2], d931[0][0], {3}, 1); // mb long
// left only c_35_ost[1] (5, 25, no35, 55, 65 ...), d71[0] (7, 49, 77, 91), c_2_357_ost[1], c_3_57_ost[2]
vector<pair<int, int>> bp = big_primes(c_2_357_ost[1], p1_11);
filter(c_3_57_ost[2], 3, bp);
filter(d71[0], 7, bp);
filter(c_35_ost[1], 5, bp);
// ost 5, 25 & 7, 49
// print(c_35_ost[1], "c_35_ost[1]");
// print(c_2_57_ost[0], "c_2_57_ost[0]");
// print(d71[0], "d71[0]");
// print(c_2_57_ost[1], "c_2_57_ost[1]");
find_p2(c_35_ost[1], c_2_57_ost[0], 25);
find_p2(d71[0], c_2_57_ost[1], 49);
// check();
cout << "! " << answer << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// ans_p.resize(100);
// iota(ans_p.begin(), ans_p.end(), 1);
for (int t = 0; t < 1000; ++t) {
mem.clear();
// random_shuffle(ans_p.begin(), ans_p.end());
// random_shuffle(ans_p.begin(), ans_p.end());
solve();
}
// cerr << ask_count << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 853ms
memory: 3880kb
input:
1 1 1 3 1 1 1 3 1 2 1 1 3 1 1 1 1 1 2 4 1 1 1 1 1 2 2 1 1 1 2 2 1 2 1 4 4 4 16 4 1 1 1 2 8 1 1 1 1 1 1 1 1 8 1 2 8 2 1 1 1 16 2 1 2 2 4 1 1 1 2 1 1 1 2 2 4 1 4 1 1 16 4 4 1 1 2 8 2 2 16 8 1 2 1 1 1 2 1 16 1 2 4 1 2 2 8 1 1 2 2 1 4 1 1 4 2 1 3 31 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 ...
output:
? 84 87 ? 78 16 ? 94 36 ? 87 93 ? 50 22 ? 63 28 ? 91 60 ? 64 27 ? 41 27 ? 73 37 ? 12 69 ? 68 30 ? 83 31 ? 63 24 ? 68 36 ? 30 3 ? 23 59 ? 70 68 ? 94 57 ? 12 43 ? 1 12 ? 2 12 ? 3 12 ? 4 12 ? 5 12 ? 6 12 ? 7 12 ? 8 12 ? 9 12 ? 10 12 ? 11 12 ? 13 12 ? 14 12 ? 15 12 ? 16 12 ? 17 12 ? 18 12 ? 19 12 ? 20 1...
result:
ok Primes are found successfully with S = 551263 queries total