#1174931 (C++23(gnu拡張gcc16)) No.3520 L1等距離点

• 問題: No.3520 L1等距離点
• ユーザー: zer0-star
• 提出日時: 2026-08-04 07:10:49
• 言語: C++23(gnu拡張gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,179 bytes
• コンパイル時間: 10,429 ms
• コンパイル使用メモリ: 480,076 KB
• 実行使用メモリ: 12,288 KB
• 最終ジャッジ日時: 2026-08-04 07:11:08
• 合計ジャッジ時間: 17,501 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
other	TLE * 1 -- * 34

ソースコード

#define USE_ACLIBRARY 0

#if __has_include(<all.hpp>)

#include <all.hpp>

#else

#include <bits/extc++.h>

#if __has_include(<atcoder/all>) || USE_ACLIBRARY

#include <atcoder/all>

#endif

#endif

#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for (ll i = (a); i < ll(b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for (ll i = (a) - 1; i >= ll(b); i--)

using ll = long long int;
using ull = unsigned long long int;

using pll = std::pair<ll, ll>;
using pil = std::pair<int, ll>;
using pli = std::pair<ll, int>;
using pii = std::pair<int, int>;

constexpr const ll INFL = 1ll << 60;

using namespace std::literals;

std::mt19937_64 rng{std::random_device()()};

template <class T>
bool chmin(T& x, const T& val) {
  if (x > val) {
    x = val;
    return true;
  } else {
    return false;
  }
}

template <class T>
bool chmin2(T& x, const T& val) {
  if (!(val < 0) and (x < 0 || x > val)) {
    x = val;
    return true;
  } else {
    return false;
  }
}

template <class T>
bool chmax(T& x, const T& val) {
  if (x < val) {
    x = val;
    return true;
  } else {
    return false;
  }
}

ll isqrt(ll n) {
  assert(n >= 0);
  if (n == 0) return 0;

  uint32_t c = (std::bit_width(uint64_t(n)) - 1) / 2;
  ll a = 1;
  ll d = 0;

  for (int s = std::bit_width(c) - 1; s >= 0; s--) {
    ll e = d;
    d = c >> s;
    a = (a << (d - e - 1)) + (n >> (2 * c - e - d + 1)) / a;
  }

  return a - (a * a > n);
}

#if __has_include(<atcoder/all>) || USE_ACLIBRARY

template <class mint, atcoder::internal::is_modint_t<mint>* = nullptr>
std::ostream& operator<<(std::ostream& os, const mint& v) {
  return os << v.val();
}

template <class mint, atcoder::internal::is_modint_t<mint>* = nullptr>
std::istream& operator>>(std::istream& is, mint& v) {
  int tmp;
  is >> tmp;
  v = tmp;
  return is;
}

template <class mint>
  requires atcoder::internal::is_modint<mint>::value
struct std::formatter<mint> : std::formatter<int> {
  template <typename FormatContext>
  auto format(const mint& x, FormatContext& context) const {
    return std::formatter<int>::format(x.val(), context);
  }
};

#endif

template <class T, class U>
std::istream& operator>>(std::istream& is, std::pair<T, U>& p) {
  return is >> p.first >> p.second;
}

template <class... T>
std::istream& operator>>(std::istream& is, std::tuple<T...>& tpl) {
  std::apply([&](auto&&... args) { (is >> ... >> args); }, tpl);
  return is;
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
  for (T& x : v) is >> x;
  return is;
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  for (size_t i = 0; i < v.size(); i++)
    os << v[i] << (i == v.size() - 1 ? "" : " ");
  return os;
}

template <class I, class T>
std::vector<T> make_vector(I n, const T& x) {
  return std::vector<T>(n, x);
}

template <class I, class J, class K, class... Ts>
auto make_vector(I i, J j, K k, Ts&&... xs) {
  return std::vector(i, make_vector(j, k, xs...));
}

struct Initialization {
  Initialization() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
  }
} initialization;

template <class... Args>
void println(std::format_string<Args...> fmt, Args&&... args) {
  std::println(std::cout, fmt, std::forward<Args>(args)...);
}

void println() {
  std::println(std::cout);
}

template <class Arg>
void println(Arg&& arg) {
  std::println(std::cout, "{}", std::forward<Arg>(arg));
}

template <class... Args>
void eprintln(std::format_string<Args...> fmt, Args&&... args) {
  std::println(std::cerr, fmt, std::forward<Args>(args)...);
}

void eprintln() {
  std::println(std::cerr);
}

template <class Arg>
void eprintln(Arg&& arg) {
  std::println(std::cerr, "{}", std::forward<Arg>(arg));
}

constexpr const std::pair<int, int> DIRS[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
constexpr const std::pair<int, int> DIRS8[] = {
    {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};

template <typename T>
using infs = std::numeric_limits<T>;

template <typename T>
using pq_rev = std::priority_queue<T, std::vector<T>, std::greater<T>>;

namespace pbds = __gnu_pbds;

template <typename T>
using tree = pbds::tree<T, pbds::null_type, std::less<T>, pbds::rb_tree_tag,
                        pbds::tree_order_statistics_node_update>;

template <typename T>
class range {
  T left, right, step;

  struct iterator {
    T val, step;

    T operator*() const { return val; }

    iterator& operator++() {
      val += step;
      return *this;
    }

    iterator& operator--() {
      val -= step;
      return *this;
    }

    constexpr bool operator!=(T rhs) const { return val != rhs; }
  };

 public:
  constexpr range(T r) : range(0, r) {}
  constexpr range(T l, T r) : range(l, r, 1) {}
  constexpr range(T l, T r, T st) : left(l), right(r), step(st) {
    if (right < left) {
      right = left;
    } else if (T m = (right - left) % step; m != 0) {
      right -= m;
      right += step;
    }
  }

  constexpr iterator begin() const { return iterator(left, step); }

  constexpr T end() const { return right; }

  constexpr inline size_t size() const { return (right - left) / step; }

  constexpr inline bool has(T x) const {
    return left <= x and x < right and (x - left) % step == 0;
  }
};

template <typename T>
struct factorials {
  static size_t n;
  static std::vector<T> fact, inv_fact;

  static inline void extend(size_t m) {
    if (m <= n) return;
    fact.resize(m + 1);
    inv_fact.resize(m + 1);
    for (size_t i = n + 1; i <= m; i++) fact[i] = fact[i - 1] * i;
    inv_fact[m] = fact[m].inv();
    for (size_t i = m; i > n + 1; i--) inv_fact[i - 1] = inv_fact[i] * i;
    n = m;
  }

  static T inv(int k) {
    extend(k);
    return inv_fact[k];
  }

  static T get(int k) {
    extend(k);
    return fact[k];
  }

  static T perm(int n, int k) {
    if (n < k) return 0;
    if (k < 0) return 0;
    extend(n);
    return fact[n] * inv_fact[n - k];
  }

  static T choose(int n, int k) {
    if (n < k) return 0;
    if (k < 0) return 0;
    extend(n);
    return fact[n] * inv_fact[n - k] * inv_fact[k];
  }

  static T catalan(int n) { return get(2 * n) * inv(n + 1) * inv(n); }
};

template <typename T>
size_t factorials<T>::n = 0;

template <typename T>
std::vector<T> factorials<T>::fact = {1};

template <typename T>
std::vector<T> factorials<T>::inv_fact = {1};

#if __has_include(<atcoder/all>) || USE_ACLIBRARY

using mint = atcoder::modint998244353;
// using mint = atcoder::modint1000000007;

using fs = factorials<mint>;

#endif

int main() {
  ll T, x0, y0, xT, yT;
  std::cin >> T >> x0 >> y0 >> xT >> yT;

  ll ok = 0, ng = T;

  auto dist = [](ll x1, ll y1, ll x2, ll y2) -> ll {
    return std::abs(x1 - x2) + std::abs(y1 - y2);
  };

  while (ng - ok > 1) {
    ll mid = (ok + ng) / 2;

    std::println("? {}", mid);
    ll x, y;
    std::cin >> x >> y;

    if (dist(x0, y0, x, y) <= dist(xT, yT, x, y)) {
      ok = mid;
    } else {
      ng = mid;
    }
  }

  std::println("! {}", ok);
}