QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#321119#8216. Jumbled Primesucup-team008#AC ✓1050ms3588kbC++178.4kb2024-02-04 04:26:022024-02-04 04:26:03

Judging History

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

  • [2024-02-04 04:26:03]
  • 评测
  • 测评结果：AC
  • 用时：1050ms
  • 内存：3588kb
查看
  • [2024-02-04 04:26:02]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(1) cerr

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << flush;
// END NO SAD

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

template<class T>
bool updmin(T& a, T b) {
  if(b < a) {
    a = b;
    return true;
  }
  return false;
}
template<class T>
bool updmax(T& a, T b) {
  if(b > a) {
    a = b;
    return true;
  }
  return false;
}
typedef int64_t ll;

mt19937 g1(0x14004);
int get_random_int(int a, int b) {
  return uniform_int_distribution<int>(a, b)(g1);
}

int lcm(int a, int b) {
  return a / gcd(a, b) * b;
}
bool isprime(int n) {
  for(int i = 2; i * i <= n; i++) if(n%i==0) return false; return true;
}
vector<int> allps = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
int cnums = 0;
int fsps = 0;
int tdp1 = 0;
int spf = 0;
int spd = 0;
int ftd = 0;
void rsolve() {
  cnums++;
  const int n = 100;
  map<array<int, 2>, int> dp;
  int numqry = 0;
  auto _qry = [&](int i, int j) -> int {
    if(i > j) swap(i, j);
    assert(0 <= i && i < j && j < n);
    array<int, 2> key = {i, j};
    if(dp.count(key)) return dp[key];
    cout << "? " << (i+1) << " " << (j+1) << endl;
    cin >> dp[key];
    numqry++;
    return dp[key];
  };
  vector<int> known(n, 1);
  map<int, set<int>> definitelynot;
  map<int, set<int>> knowngood;
  vector<bool> composite(n);
  auto doqry = [&](int a, int b) -> void {
    if(a < 0 || b < 0 || a == b) return;
    int x = _qry(a, b);
    for(int out: allps) {
      if(known[a] % out == 0) knowngood[out].insert(a);
      if(known[b] % out == 0) knowngood[out].insert(b);
      if(known[a] % out == 0 && x % out != 0) definitelynot[out].insert(b);
      if(known[b] % out == 0 && x % out != 0) definitelynot[out].insert(a);
    }
    known[a] = lcm(known[a], x);
    known[b] = lcm(known[b], x);
    if(!isprime(known[a])) composite[a] = true;
    if(!isprime(known[b])) composite[b] = true;
  };
  vector<int> smallps = {2, 3, 5, 7};
  vector<int> indices = {-1, -1, -1, -1};
  int knownsix = -1;
  while(true) {
    bool done = true;
    for(int i = 0; i < 4; i++) {
      if(indices[i] == -1) {
        int a = get_random_int(0, n-1);
        while(definitelynot[smallps[i]].count(a)) a = get_random_int(0, n-1);
        int b = get_random_int(0, n-1);
        while(definitelynot[smallps[i]].count(b) || a == b) b = get_random_int(0, n-1);
        doqry(a, b);
        if(known[a]%6 == 0) {
          knownsix = a;
        }
        for(int j = 0; j < 4; j++) {
          if(indices[j] == -1 && known[a]%smallps[j] == 0) {
            indices[j] = a;
          }
        }
        if(indices[i] == -1) {
          done = false;
          break;
        }
      }
    }
    if(done) break;
  }
  for(int i = 0; i < n; i++) {
    if(!isprime(known[i])) {
      composite[i] = true;
      continue;
    }
    doqry(i, knownsix);
    if(knownsix >= 0) {
      for(int a = 2; a < 4 && !composite[i]; a++) {
        if(definitelynot[smallps[a]].count(i)) continue;
        if(known[i] % smallps[a] == 0) continue;
        doqry(i, indices[a]);
        if(!isprime(known[i])) {
          if(known[i] % 6 == 0 && knownsix < 0) knownsix = i;
          break;
        }
      }
    }
    else {
      for(int a = 0; a < 4 && !composite[i]; a++) {
        if(definitelynot[smallps[a]].count(i)) continue;
        if(known[i] % smallps[a] == 0) continue;
        doqry(i, indices[a]);
        if(!isprime(known[i])) {
          if(known[i] % 6 == 0 && knownsix < 0) knownsix = i;
          break;
        }
      }
    }
  }
  vector<int> primesquareindices(4, -1);
  for(int i = 0; i < n; i++) {
    for(int a = 0; a < 4; a++) {
      if(known[i] % (smallps[a] * smallps[a]) == 0) {
        primesquareindices[a] = i;
        break;
      }
    }
  }
  while(true) {
    bool done = true;
    for(int a = 0; a < 4; a++) {
      if(primesquareindices[a] == -1) {
        vector<int> candidates;
        for(int i = 0; i < n; i++) {
          if(definitelynot[smallps[a]].count(i)) continue;
          if(known[i] % smallps[a] == 0) candidates.pb(i);
        }
        assert(sz(candidates) > 1);
        shuffle(all(candidates), g1);
        doqry(candidates[0], candidates[1]);
        if(known[candidates[0]]%(smallps[a]*smallps[a]) == 0) {
          primesquareindices[a] = candidates[0];
          continue;
        }
        done = false;
        break;
      }
    }
    if(done) break;
  }
  for(int a = 0; a < 4; a++) {
    for(int i = 0; i < n; i++) {
      if(definitelynot[smallps[a]].count(i)) continue;
      if(composite[i]) continue;
      doqry(i, primesquareindices[a]);
    }
  }
  map<int, int> primetoindices;
  vector<int> primecandidates;
  for(int i = 0; i < n; i++) {
    if(composite[i]) continue;
    if(known[i] == 1) primecandidates.pb(i);
    else {
      assert(isprime(known[i]));
      primetoindices[known[i]] = i;
    }
  }
  for(int pidx = 0; pidx < 4; pidx++) {
    set<int> alreadyused;
    for(int i = 0; i < n; i++) {
      if(composite[i] || known[i] % smallps[pidx]) continue;
      for(auto [k, v]: primetoindices) {
        if(alreadyused.count(v)) continue;
        if(known[i] * k > n) break;
        if(definitelynot[k].count(i)) continue;
        if(sz(knowngood[k]) && n / sz(knowngood[k]) == n / k) continue;
        doqry(i, v);
        if(composite[i]) {
          alreadyused.insert(v);
          break;
        }
      }
      for(int a = sz(primecandidates)-1; a >= 0 && !composite[i]; a--) {
        int cidx = primecandidates[a];
        if(cidx == i) continue;
        doqry(cidx, i);
        if(composite[i]) {
          alreadyused.insert(cidx);
        }
        if(known[cidx] > 1) {
          assert(isprime(known[cidx]));
          primecandidates.erase(primecandidates.begin() + a);
          primetoindices[known[cidx]] = cidx;
        }
      }
      if(composite[i]) continue;
    }
  }
  for(int i = 0; i < n; i++) {
    if(!isprime(known[i])) composite[i] = true;
  }
  cout << "! ";
  for(int i = 0; i < n; i++) cout << "10"[composite[i]];
  cout << endl;
}
void solve() {
  for(int q = 0; q < 1000; q++) rsolve();
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1050ms
memory: 3588kb

input:

1
3
1
1
1
1
2
2
3
1
1
2
1
2
1
1
1
1
1
1
1
15
1
7
1
3
3
1
1
7
1
1
1
1
1
1
25
1
3
1
2
1
1
2
1
25
1
1
1
1
1
1
1
1
5
2
1
1
2
1
1
2
9
3
3
1
2
1
14
1
1
1
6
10
2
2
2
2
30
9
1
1
15
2
6
3
1
1
1
1
1
1
1
3
1
5
1
9
1
1
10
3
7
2
2
18
2
2
5
1
1
1
1
1
2
2
2
2
10
1
1
18
2
2
1
1
5
1
1
6
1
7
3
1
2
2
10
2
2
1
1
2
2
3
...

output:

? 9 34
? 26 54
? 2 19
? 92 93
? 43 87
? 27 34
? 25 71
? 58 72
? 5 99
? 11 22
? 2 63
? 47 77
? 53 55
? 19 93
? 41 43
? 16 67
? 78 88
? 41 80
? 41 60
? 31 55
? 30 75
? 47 91
? 50 89
? 51 70
? 1 25
? 1 54
? 1 91
? 1 70
? 2 25
? 2 54
? 2 91
? 3 25
? 3 54
? 3 91
? 4 25
? 4 54
? 4 91
? 5 25
? 5 91
? 5 70
...

result:

ok Primes are found successfully with S = 501670 queries total
English 繁體中文 简体中文

Server Time: 2024-12-01 00:41:03 | OpenSource Project