乱搞

ottora · 2024-02-28 13:14:25 · 题解

考虑随机化。

先随机 m 次询问，再枚举序列长度 n 并检查是否合法。

注意到长度为 m 的循环单峰排列是 O\left(n^3\right) 的（A060354），因此当 m = O\left(\log N\right) 时即可求出唯一的 n。

之后倍增求最大值是简单的。

期望询问次数 O\left(\log N\right)，实际上非常优秀，在本题数据范围下几乎不超过 100 次询问。

代码

#include <bits/stdc++.h>
using namespace std;
int ask(int);
int cheat();
vector<int> B; vector<int64_t> X;
vector<pair<int, int>> V;
bool check(int n, int q){
  V.clear();
  for(int i = 0; i <  q; i++) V.emplace_back(X[i] % n, B[i]);
  sort(V.begin(), V.end());
  for(int i = 0; i <  q; i++)
    if(V[i].first == (V[(i + 1) % q].first) && V[i].second != (V[(i + 1) % q].second)) return 0;
  V.erase(unique(V.begin(), V.end()), V.end()), q = V.size();
  if(q > 2) for(int i = 0; i <  q; i++)
    if(V[i].second == V[(i + 1) % q].second && V[i].second == V[(i + 2) % q].second) return 0;
  int mx = 0, mn = 0;
  for(int i = 0; i <  q; i++) if(V[i].second > V[mx].second) mx = i;
  for(int i = 0; i <  q; i++) if(V[i].second < V[mn].second) mn = i;
  for(int i = mn, lst = INT_MIN; i != mx; ++i >= q && (i = 0))
    if(V[i].second < lst) return 0; else lst = V[i].second;
  for(int i = mx, lst = INT_MAX; i != mn; ++i >= q && (i = 0))
    if(V[i].second > lst) return 0; else lst = V[i].second;
  return 1;
}
int buer(int){
  mt19937 rnd(time(0));
  vector<int> Ans;
  for(int i = 2; i <= 1000000; i++) Ans.push_back(i);
  int64_t x = 0;
  for(int q = 1; Ans.size() > 1; q++){
    int k = rnd() % 1000000000 + 1;
    X.push_back(x += k), B.push_back(ask(k));
    if(q > 5){
      vector<int> Now;
      for(int i: Ans) if(check(i, q)) Now.push_back(i);
      Ans = Now;
    }
  }
  int n = Ans.back(), id = 0;
  for(int i = 0; i < (int)X.size(); i++) if(B[i] > B[id]) id = i;
  int p = ask((X[id] - x) % n + n), q = ask(1); id = (X[id] + 1) % n;
  if(p < q){
    int v = q;
    for(int k = 20; k >= 0; k--){
      p = ask(1 << k), q = ask(1);
      if(v < p && p < q) id = (id + (1 << k) + 1) % n, v = q;
      else ask((n - (1 << k) - 1) % n + n);
    } return max(v, ask(1));
  } else {
    int v = q;
    for(int k = 20; k >= 0; k--){
      p = ask((n - (1 << k)) % n + n), q = ask(n - 1);
      if(v < p && p < q) id = (id + n * 2 - (1 << k) - 1) % n, v = q;
      else ask((1 << k) + 1);
    } return max(v, ask(n - 1));
  }
  return 0;
}