結果

問題 No.2962 Sum Bomb Bomber
コンテスト
ユーザー liveworldlike
提出日時 2024-11-16 16:26:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,955 bytes
コンパイル時間 1,549 ms
コンパイル使用メモリ 73,548 KB
実行使用メモリ 25,692 KB
平均クエリ数 18.09
最終ジャッジ日時 2024-11-16 16:26:55
合計ジャッジ時間 9,858 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

// $(DATE)
// Problem "$(PROBLEM)" in contest "$(CONTEST)"
#include <map>
#pragma GCC optimize("O3")
#include <stdio.h>
#ifdef NOJUDGE
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
using namespace std;
typedef long long int ll;

inline ll query(ll x, ll y) {
  printf("1 %lld %lld\n", x, y);
  fflush(stdout);
  ll ans;
  scanf("%lld", &ans);
  return ans;
}

struct Q {
  struct P {
    ll a, b;
    bool operator<(P other) const {
      return a == other.a ? b < other.b : a < other.a;
    }
  };
  map<P, ll> cache;
  ll operator()(ll x, ll y) {
    if (!cache.count({x, y})) {
      cache[{x, y}] = query(x, y);
    }
    return cache[{x, y}];
  }
};

const ll H = 10;
const ll L = -H;

inline void solve() {
  ll n;
  scanf("%lld", &n);
  Q q;
  ll x, y;
  ll low = L, high = H;
  while (high - low > 2) {
    ll third = (high - low) / 3;
    ll mid1 = low + third;
    ll mid2 = low + 2 * third;
    debug("low=%lld m1=%lld m2=%lld high=%lld\n", low, mid1, mid2, high);
    if (q(mid1, 0) >= q(mid2, 0)) {
      low = mid1;
    } else {
      high = mid2;
    }
    debug("q(%lld, 0) = %lld q(%lld, 0) = %lld\n", mid1, q(mid1, 0), mid2,
          q(mid2, 0));
  }
  x = low;
  for (ll i = low + 1, v = q(low, 0); i < high; i++) {
    if (q(i, 0) < v) {
      x = i;
      v = q(i, 0);
    }
  }
  debug("Determined x as %lld\n", x);
  low = L, high = H;
  while (high - low > 2) {
    ll third = (high - low) / 3;
    ll mid1 = low + third;
    ll mid2 = low + 2 * third;
    if (q(0, mid1) >= q(0, mid2)) {
      low = mid1;
    } else {
      high = mid2;
    }
  }
  y = low;
  for (ll i = low + 1, v = q(0, low); i < high; i++) {
    if (q(0, i) < v) {
      y = i;
      v = q(i, 0);
    }
  }
  printf("2 %lld %lld\n", x, y);
}

#define $(JUDGE)

int main() {
#if defined(Codeforces) || defined(CodeChef)
  ll t;
  scanf("%lld", &t);
  for (int i = 0; i < t; i++) {
    solve();
  }
#else
  solve();
#endif
}
0