QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#321445 | #8216. Jumbled Primes | hos_lyric | AC ✓ | 605ms | 3868kb | C++14 | 5.5kb | 2024-02-04 19:10:03 | 2024-02-04 19:10:03 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
#ifdef LOCAL
// #define DEB
#endif
constexpr int N = 100;
constexpr int PS[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
#ifdef DEB
map<int, int> stats;
int secret[N + 1];
void gen(int seed) {
mt19937_64 gnr(seed);
for (int a = 1; a <= N; ++a) secret[a] = a;
for (int a = 1; a <= N; ++a) swap(secret[1 + gnr() % a], secret[a]);
}
#endif
int Q;
int cache[N + 1][N + 1];
int lcms[N + 1];
void init() {
Q = 0;
memset(cache, 0, sizeof(cache));
fill(lcms + 1, lcms + (N + 1), 1);
}
int ask(int a, int b) {
assert(1 <= a); assert(a <= N);
assert(1 <= b); assert(b <= N);
assert(a != b);
if (a > b) swap(a, b);
int &ret = cache[a][b];
if (!ret) {
++Q;
#ifdef DEB
ret = __gcd(secret[a], secret[b]);
#else
printf("? %d %d\n", a, b);
fflush(stdout);
scanf("%d", &ret);
#endif
lcms[a] = lcms[a] / __gcd(lcms[a], ret) * ret;
lcms[b] = lcms[b] / __gcd(lcms[b], ret) * ret;
}
return ret;
}
void answer(const string &str) {
#ifdef DEB
assert((int)str.size() == N + 1);
for (int a = 1; a <= N; ++a) {
const int pos = lower_bound(PS, PS + 25, secret[a]) - PS;
const char expected = (secret[a] == 1 || (pos < 25 && PS[pos] == secret[a])) ? '1' : '0';
if (expected != str[a]) {
cerr << "FAIL: a = " << a << ", secret[a] = " << secret[a] << ", expected = " << expected << ", str[a] = " << str[a] << endl;
}
assert(expected == str[a]);
}
#else
printf("! %s\n", str.substr(1).c_str());
fflush(stdout);
#endif
}
#include <chrono>
#ifdef LOCAL
mt19937_64 rng(58);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
void run(int seed) {
#ifdef DEB
gen(seed);
#endif
init();
constexpr int M = 2*3*5*7;
for (int i = 4; --i >= 0; ) {
int a = 0;
for (int b = 1; b <= N; ++b) if (lcms[b] % PS[i] == 0) {
a = b;
break;
}
if (!a) {
for (; ; ) {
a = 1 + rng() % N;
const int b = 1 + rng() % N;
if (a != b && ask(a, b) % PS[i] == 0) {
break;
}
}
}
for (int b = 1; b <= N; ++b) if (lcms[b] % PS[i] != 0) {
ask(a, b);
}
}
// cerr<<"lcms = ";for(int x=1;x<=N;++x)cerr<<lcms[find(secret,secret+(N+1),x)-secret]<<" ";cerr<<endl;
vector<int> ass[5];
for (int i = -1; i < 4; ++i) {
const int p = (~i) ? PS[i] : 1;
for (int a = 1; a <= N; ++a) if (__gcd(lcms[a], M) == p) {
ass[1 + i].push_back(a);
}
for (int j = 0; j < (int)ass[1 + i].size(); ++j) {
swap(ass[1 + i][rng() % (j + 1)], ass[1 + i][j]);
}
// cerr<<i<<": ";for(const int a:ass[1+i])cerr<<secret[a]<<" ";cerr<<endl;
}
/*
Q := {11, ..., 97}
1, Q
2 [, 4, 8, 16, 32, 64, 2 Q, 4 Q, 8 Q]
3 [, 9, 27, 81, 3 Q, 9 Q]
5 [, 25, 5 Q]
7 [, 49, 7 Q]
*/
#ifdef DEB
stats[__LINE__]+=Q;
#endif
for (int i = 4; --i >= 0; ) {
vector<int> bs;
for (int b = 1; b <= N; ++b) if (__gcd(lcms[b], M * M) == ((i == 0) ? 1 : PS[i - 1])) {
bs.push_back(b);
}
for (int j = 0; j < (int)bs.size(); ++j) {
swap(bs[rng() % (j + 1)], bs[j]);
}
// cerr<<"i = "<<i<<", bs: ";for(const int b:bs)cerr<<secret[b]<<" ";cerr<<endl;
vector<int> as;
for (const int a : ass[1 + i]) {
#define check if (PS[i] % lcms[a] != 0) goto failed; {}
check;
for (const int b : bs) {
ask(a, b);
check;
}
{
// 4 * 3*7, 9 * 2*5, 25 * 3, 49 * 2
constexpr int MS[4] = {2 * 3*7, 3 * 2*5, 5 * 3, 7 * 2};
for (int b = 1; b <= N; ++b) if (lcms[b] % MS[i] == 0) {
ask(a, b);
check;
}
ass[1 + i] = {a};
break;
}
failed:{}
#undef check
}
// cerr<<i<<": ";for(const int a:ass[1+i])cerr<<secret[a]<<" ";cerr<<endl;
#ifdef DEB
stats[__LINE__-i]+=Q;
#endif
}
#ifdef DEB
stats[__LINE__]+=Q;
#endif
string ans(N + 1, '0');
for (int i = -1; i < 4; ++i) {
for (const int a : ass[1 + i]) {
ans[a] = '1';
}
}
answer(ans);
}
int main() {
for (int seed = 0; seed < 1000; ++seed) {
run(seed);
}
#ifdef DEB
cerr << "stats = "; pv(stats.begin(), stats.end());
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 605ms
memory: 3868kb
input:
1 8 1 1 1 1 1 2 1 2 1 4 15 1 1 1 3 1 5 1 3 1 1 1 2 2 1 1 1 1 1 1 1 4 1 1 12 4 8 1 1 2 19 1 4 15 1 1 2 3 2 1 1 1 2 2 1 1 2 1 2 1 1 5 5 3 3 9 1 2 26 1 2 2 1 1 5 1 7 1 7 1 5 1 2 10 1 1 5 2 2 10 1 14 1 10 2 2 10 1 1 5 2 2 1 1 1 1 1 5 1 1 10 7 2 2 5 1 1 2 2 10 1 10 2 1 35 1 2 7 1 2 2 1 2 1 1 2 2 14 5 1 1...
output:
? 8 37 ? 38 90 ? 12 50 ? 8 70 ? 5 86 ? 4 68 ? 20 22 ? 37 47 ? 34 82 ? 13 94 ? 78 81 ? 49 99 ? 24 67 ? 80 82 ? 4 66 ? 42 71 ? 27 65 ? 41 73 ? 10 45 ? 38 78 ? 14 54 ? 9 73 ? 2 95 ? 28 54 ? 37 58 ? 45 88 ? 15 60 ? 8 73 ? 9 28 ? 24 86 ? 3 64 ? 12 28 ? 33 84 ? 75 99 ? 20 33 ? 31 49 ? 17 65 ? 18 26 ? 44 7...
result:
ok Primes are found successfully with S = 549182 queries total