結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<VL> VVL;
typedef long long LL;
#define all(a) (a).begin(), (a).end()
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back



int main() {

  VI X,Y;
  queue<VI> D;
  D.push({0,1000000});
  while(D.size()>0){
    VI z=D.front(); D.pop();
    if(z[0]==z[1]){X.pb(z[0]);continue;}
    int r=(z[0]+z[1])/2;
    bool h;
    cout<<"? "<<z[0]<<' '<<r<<' '<<0<<' '<<1000000<<endl;
    cin>>h;
    if(h){D.push({z[0],r});}
    cout<<"? "<<r+1<<' '<<z[1]<<' '<<0<<' '<<1000000<<endl;
    cin>>h;
    if(h){D.push({r+1,z[1]});}
  }
  
  D.push({0,1000000});
  while(D.size()>0){
    VI z=D.front(); D.pop();
    if(z[0]==z[1]){Y.pb(z[0]);continue;}
    int r=(z[0]+z[1])/2;
    bool h;
    cout<<"? "<<0<<' '<<1000000<<' '<<z[0]<<' '<<r<<endl;
    cin>>h;
    if(h){D.push({z[0],r});}
    cout<<"? "<<0<<' '<<1000000<<' '<<r+1<<' '<<z[1]<<endl;
    cin>>h;
    if(h){D.push({r+1,z[1]});}
  }
  sort(all(Y));
  int m=Y.size();
  VVI ans;
  for(int x : X){
    D.push({0,m-1});
    while(D.size()>0){
      VI z=D.front();D.pop();
      if(z[0]==z[1]){
        ans.pb({x,Y[z[0]]});
        continue;
      }
      int r=(z[0]+z[1])/2;
      bool h;
      cout<<"? "<<x<<' '<<x<<' '<<Y[z[0]]<<' '<<Y[r]<<endl;
      cin>>h;
      if(h){D.push({z[0],r});}
      cout<<"? "<<x<<' '<<x<<' '<<Y[r+1]<<' '<<Y[z[1]]<<endl;
      cin>>h;
      if(h){D.push({r+1,z[1]});}
    }
  }
  cout<<"! "<<ans.size()<<endl;
  for(VI z : ans){
    cout<<z[0]<<' '<<z[1]<<endl;
  }
}
0