結果

問題 No.3161 Find Presents
ユーザー hirakich1000000007
提出日時 2025-05-23 20:11:16
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 266 ms / 4,000 ms
コード長 1,699 bytes
コンパイル時間 6,530 ms
コンパイル使用メモリ 216,316 KB
実行使用メモリ 26,216 KB
平均クエリ数 3456.55
最終ジャッジ日時 2025-05-23 20:11:39
合計ジャッジ時間 20,075 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 80
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef pair<__int128_t, __int128_t> P128;


template<class T1, class T2>
pair<T1, T2> operator+ (const pair<T1, T2> &l, const pair<T1, T2> &r) {
	return {l.first + r.first, l.second + r.second};
}
template<class T1, class T2>
pair<T1, T2> operator- (const pair<T1, T2> &l, const pair<T1, T2> &r) {
	return {l.first - r.first, l.second - r.second};
}

pair<__int128_t, bool> deduce1 (P128 p, __int128_t a0, __int128_t val) {
	__int128_t war = val - p.first * a0;

	return {war / p.second, (war % p.second == 0)};
}
// pair<__int128_t, bool> deduce1 (__int128_t p, __int128_t val) {
// 	return {val / p, (val % p == 0)};
// }

vector<P> ans;
vector<ll> xs;

const ll MIN_A = 0, MAX_A = 1'000'000;

bool query (ll xl, ll xr, ll yl, ll yr) {
	cout << "? " << xl << " " << (xr-1) << " " << yl << " " << (yr-1) << endl;
	int ret;
	cin >> ret;
	return (bool)ret;
}

bool ask (ll l, ll r, ll mode) {
	if (mode == -1) {
		return query(l, r, MIN_A, MAX_A + 1);
	} else {
		return query(mode, mode + 1, l, r);
	}
}
void record (ll x, ll mode) {
	if (mode == -1) {
		xs.push_back(x);
	} else {
		ans.push_back({mode, x});
	}
}

void seekdfs (ll l, ll r, ll mode) {
	if (ask(l, r, mode)) {
		if (l + 1 == r) {
			record(l, mode);
		} else {
			seekdfs(l, (l+r)/2, mode);
			seekdfs((l+r)/2, r, mode);
		}
	}
}

void seek (ll mode) {
	seekdfs(MIN_A, MAX_A + 1, mode);

}

void output () {
	cout << "! " << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i].first << " " << ans[i].second << endl;
	}
}

int main (void) {
	seek(-1);
	for (ll x : xs) {
		seek(x);
	}

	output();

	return 0;
}
0