#1138164 (C++23) No.3416 マッチ棒パズル Extra

• 問題: No.3416 マッチ棒パズル Extra
• ユーザー: Nachia
• 提出日時: 2025-12-03 06:36:59
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,427 bytes
• コンパイル時間: 1,168 ms
• コンパイル使用メモリ: 112,172 KB
• 実行使用メモリ: 103,600 KB
• 最終ジャッジ日時: 2025-12-22 23:31:04
• 合計ジャッジ時間: 41,128 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
other	AC * 15 WA * 11

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;


template<class F>
ll max_f_true(const F& f, ll ok, ll ng){
  while(ok + 1 < ng){
    ll wj = (ok + ng) / 2;
    (f(wj) ? ok : ng) = wj;
  }
  return ok;
}

template<class F>
ll expsearch(const F& f, ll maxval = INF){
  ll l = 0, r = 1;
  while(r < maxval && f(r)){ l = r; r *= 2; r = min(r, maxval); }
  return max_f_true(f, l, r);
}

struct ConvexEdge {
    ll dx;
    ll dy;
    ll count;
};
struct Convex {
    vector<ConvexEdge> edges;
};

// x,y 両方に関して単調増加凸関数 f について、 
// 0 <= x, 0 <= y , f(x,y) < 0 なる (x,y) の集合の凸包を求める。
// start, end はともに f(x,y) < 0 を満たし、探索領域の右下と左上を指す。
template<class F>
Convex ConvexTrace(
  const F& f, pair<ll, ll> start, pair<ll, ll> end
){
  ll minx = end.first;
  ll maxx = start.first;
  ll maxy = end.second;
  auto det = [&](ll x, ll y) -> bool { return f(x,y) < 0; };
  auto inrange = [&](ll x, ll y) -> bool { return minx <= x && y <= maxy; };
  auto fp = [&](ll x, ll y){
      return x <= maxx && y <= maxy && (x < minx || y < 0 || det(x, y));
  };

  Convex res;
  ll x = start.first, y = start.second;

  struct Node { ll ldx, ldy, rdx, rdy; };
  
  vector<Node> sch;
  sch.push_back({ 0, 1, 1, 0 });
  {
    ll w = expsearch([&](ll t){ return fp(maxx, y + t); });
    if(w){
      y += w;
      res.edges.push_back({ 0, 1, w });
    }
  }

  while(minx < x && y < maxy && sch.size()){
    auto v = sch.back();
    
    if(!fp(x - v.rdx, y + v.rdy)){
      sch.pop_back();
      continue;
    }
    ll maxlsh = expsearch([&](ll t){ return fp(x - v.ldx * t - v.rdx, y + v.ldy * t + v.rdy); });
    if(maxlsh >= 1){
      ll nxdx = v.ldx * maxlsh + v.rdx;
      ll nxdy = v.ldy * maxlsh + v.rdy;
      sch.push_back({ nxdx + v.ldx, nxdy + v.ldy, nxdx, nxdy });
      continue;
    }
    auto pred = [&](ll t) -> bool {
      ll qx = x - v.ldx - v.rdx * t, qy = y + v.ldy + v.rdy * t;
      if(!inrange(qx - v.rdx, qy + v.rdy)) return 0;
      ll lval = f(qx, qy);
      if(lval < 0) return 0;
      ll rval = f(qx - v.rdx, qy + v.rdy);
      return rval < lval;
    };
    ll t = expsearch(pred);
    Node nx = { v.ldx + v.rdx * t, v.ldy + v.rdy * t, v.ldx + v.rdx * (t+1), v.ldy + v.rdy * (t+1) };
    if(inrange(x - nx.rdx, y + nx.rdy) && f(x - nx.rdx, y + nx.rdy) < 0){
      sch.push_back(nx);
      continue;
    }
    ll w = expsearch([&](ll w){ return fp(x - v.rdx * w, y + v.rdy * w); });
    if(w){
      res.edges.push_back({ v.rdx, v.rdy, w });
      x -= v.rdx * w; y += v.rdy * w;
    }
    sch.pop_back();
  }

  if(end.first < x) res.edges.push_back({ 1, 0, x - end.first });
  return res;
}


const int MOD = 998244353;

void testcase(){
  ll N; cin >> N;
  auto det = [&](ll a, ll b) -> bool { return __int128_t(a) * b * 2 + a + b <= N; };
  auto maxb = [&](ll a) -> ll { return expsearch([a,det](ll b){ return det(a, b); }); };
  ll maxdiag = expsearch([&](ll x){ return det(x,x); });
  ll max1b = expsearch([&](ll x){ return det(1,x); });

  auto tr = [&](ll x){ return max1b + 1 - x; };
  auto convexdet = 
    [&](ll x, ll y) -> __int128_t {
      ll a = max1b + 1 - x, b = max1b + 1 - y;
      return N - __int128_t(a) * b * 2 - a - b;
    };

  ll naive_lim = min<ll>(maxdiag, 10000000);
  ll offset = naive_lim + 1;
  pair<ll, ll> ct_start = { maxb(offset) + 1, offset };

  ll ans = 0;
  for(ll i=1; i<=naive_lim; i++){
    ans += (((N * 2 + 1) / (i * 2 + 1) - 1) / 2 - i) * 2;
    ans %= MOD;
  }
  ans += naive_lim;

  auto ch = ConvexTrace(convexdet,
    {tr(maxdiag+1), tr(maxdiag+1)},
    {tr(ct_start.first), tr(ct_start.second)});
  reverse(ch.edges.begin(), ch.edges.end());
  
  ll onborder = (ct_start.first - 1 - offset + 1) - 1;
  ll area = 0;
  
  {
    ll px = ct_start.first - offset, py = ct_start.second - offset;
    for(auto v : ch.edges){
      onborder -= v.count;
      ll qx = px - v.count * v.dx;
      ll qy = py + v.count * v.dy;
      area += (px % MOD * (qy % MOD) % MOD) - (py % MOD * (qx % MOD) % MOD);
      px = qx; py = qy;
    }
  }

  area += onborder;
  area += 1;
  area = (area % MOD + MOD) % MOD;

  ans = (ans + area) % MOD;
  
  cout << ans << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  int T; cin >> T;
  for(int i=0; i<T; i++) testcase();
  return 0;
}