結果

問題 No.3161 Find Presents
コンテスト
ユーザー butsurizuki
提出日時 2025-05-23 17:57:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 151 ms / 4,000 ms
コード長 1,032 bytes
コンパイル時間 2,991 ms
コンパイル使用メモリ 278,472 KB
実行使用メモリ 26,216 KB
平均クエリ数 2100.30
最終ジャッジ日時 2025-05-23 17:57:38
合計ジャッジ時間 15,226 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 80
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int ask(int xl,int xr,int yl,int yr){
  cout << "?";
  cout << " " << xl;
  cout << " " << xr;
  cout << " " << yl;
  cout << " " << yr;
  cout << "\n";
  fflush(stdout);

  int res;
  cin >> res;
  return res;
}

void ans(vector<pi> &a){
  cout << "! " << a.size() << "\n";
  for(auto &nx : a){
    cout << nx.first << " " << nx.second << "\n";
  }
  fflush(stdout);
}

const int sz=1000000;

int main(){
  vector<pi> res;
  int xl=0,xr=sz;
  while(xl<=xr){
    if(ask(xl,xr,0,sz)==0){
      break;
    }
    int ml=xl,mr=xr;
    while(ml<=mr){
      int te=(ml+mr)/2;
      if(ask(xl,te,0,sz)==0){ml=te+1;}
      else{mr=te-1;}
    }

    int m=ml;
    int yl=0,yr=sz;
    while(yl<=yr){
      if(ask(m,m,yl,yr)==0){break;}
      int nl=yl,nr=yr;
      while(nl<=nr){
        int te=(nl+nr)/2;
        if(ask(m,m,yl,te)==0){nl=te+1;}
        else{nr=te-1;}
      }
      res.push_back({m,nl});
      yl=nl+1;

    }

    xl=m+1;
  }
  ans(res);
  return 0;
}
0