QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#321445#8216. Jumbled Primeshos_lyricAC ✓605ms3868kbC++145.5kb2024-02-04 19:10:032024-02-04 19:10:03

Judging History

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

  • [2024-02-04 19:10:03]
  • 评测
  • 测评结果:AC
  • 用时:605ms
  • 内存:3868kb
  • [2024-02-04 19:10:03]
  • 提交

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