結果

問題 No.3161 Find Presents
ユーザー tnakao0123
提出日時 2025-05-24 19:10:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 249 ms / 4,000 ms
コード長 1,365 bytes
コンパイル時間 976 ms
コンパイル使用メモリ 65,204 KB
実行使用メモリ 26,216 KB
平均クエリ数 3351.21
最終ジャッジ日時 2025-05-24 19:10:24
合計ジャッジ時間 16,187 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 80
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int query(int, int, int, int)’:
main.cpp:35:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |     scanf("%d", &r);
      |     ~~~~~^~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3161.cc:  No.3161 Find Presents - yukicoder
 */

#include<cstdio>
#include<queue>
#include<algorithm>
#include<tuple>

using namespace std;

/* constant */

const int MAX_N = 100;
const int MAX_X = 1000000;
const int MAX_Y = 1000000;

/* typedef */

using tp4 = tuple<int,int,int,int>;
using qtp4 = queue<tp4>;

/* global variables */

int xs[MAX_N], ys[MAX_N];

/* subroutines */

int query(int x0, int x1, int y0, int y1) { // [x0,x1), [y0, y1)
  if (x0 < x1 && y0 < y1) {
    printf("? %d %d %d %d\n", x0, x1 - 1, y0, y1 - 1); fflush(stdout);

    int r;
    scanf("%d", &r);
    if (r < 0) exit(0);
    return r;
  }
  return 0;
}

/* main */

int main() {
  int n = 0;
  
  qtp4 q;
  q.push({0, MAX_X + 1, 0, MAX_Y + 1});

  while (! q.empty()) {
    auto [x0, x1, y0, y1] = q.front(); q.pop();

    if (x0 + 1 < x1 || y0 + 1 < y1) {
      int x2 = (x0 + x1) / 2, y2 = (y0 + y1) / 2;
      if (query(x0, x2, y0, y2)) q.push({x0, x2, y0, y2});
      if (query(x2, x1, y0, y2)) q.push({x2, x1, y0, y2});
      if (query(x0, x2, y2, y1)) q.push({x0, x2, y2, y1});
      if (query(x2, x1, y2, y1)) q.push({x2, x1, y2, y1});
    }
    else
      xs[n] = x0, ys[n] = y0, n++;
  }

  printf("! %d\n", n);
  for (int i = 0; i < n; i++) printf("%d %d\n", xs[i], ys[i]);
  fflush(stdout);

  //for (int i = 0; i < 1e9; i++);
  return 0;
}
0