結果

問題 No.3161 Find Presents
コンテスト
ユーザー nouka28
提出日時 2025-05-23 20:10:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 252 ms / 4,000 ms
コード長 1,384 bytes
コンパイル時間 5,411 ms
コンパイル使用メモリ 332,820 KB
実行使用メモリ 26,216 KB
平均クエリ数 3406.26
最終ジャッジ日時 2025-05-23 20:11:13
合計ジャッジ時間 19,564 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 80
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

// struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_;

signed main(){

	const int C=1000000;

	vector<int> ans_i;

	auto query=[&](int li,int ri,int lj,int rj){
		cout<<"? "<<li<<" "<<ri-1<<" "<<lj<<" "<<rj-1<<endl;
		int x;cin>>x;
		return x;
	};

	{

		auto dfs=[&](auto dfs,int l,int r){
			if(r-l==1){
				ans_i.push_back(l);
				return;
			}else{
				int m=(l+r)>>1;
				
				if(query(l,m,0,C+1))dfs(dfs,l,m);
				if(query(m,r,0,C+1))dfs(dfs,m,r);
			}
		};

		dfs(dfs,0,C+1);
	}

	vector<pair<int,int>> ans;

	auto slv=[&](int i){
		auto dfs=[&](auto dfs,int l,int r){
			if(r-l==1){
				ans.push_back({i,l});
				return;
			}else{
				int m=(l+r)>>1;
				
				if(query(i,i+1,l,m))dfs(dfs,l,m);
				if(query(i,i+1,m,r))dfs(dfs,m,r);
			}
		};
		dfs(dfs,0,C+1);
	};

	for(auto&&i:ans_i)slv(i);

	cout<<"! "<<ans.size()<<endl;

	for(auto&&[i,j]:ans){
		cout<<i<<" "<<j<<endl;
	}
}
0