QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#845747#2567. Hidden RookzhenghanyunAC ✓1064ms4744kbC++145.0kb2025-01-06 18:53:482025-01-06 18:53:49

Judging History

你现在查看的是最新测评结果

  • [2025-01-06 18:53:49]
  • 评测
  • 测评结果：AC
  • 用时：1064ms
  • 内存：4744kb
查看
  • [2025-01-06 18:53:48]
  • 提交

answer

#pragma GCC optimize(0)
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());

int T, n, m, x, y, askCnt;

inline int ask(int l1, int r1, int l2, int r2) {
#ifdef LOCAL
	++askCnt;
	int res = 0;
	for (int i = l1; i <= r1; ++i) {
		for (int j = l2; j <= r2; ++j) {
			if (x == i || y == j) {
				++res;
			}
		}
	}
	return res;
#else
	cout << "? " << l1 << " " << l2 << " " << r1 << " " << r2 << endl;
	int res;
	cin >> res;
	return res;
#endif
}

inline void print_ans(int ansX, int ansY) {
#ifdef LOCAL
	assert(ansX == x && ansY == y && askCnt <= 4);
#else
	cout << "! " << ansX << " " << ansY << endl;
#endif
}

inline void init() {
	n = rng() % 13 + 3, m = rng() % 13 + 3;
	x = rng() % n + 1, y = rng() % m + 1;
	askCnt = 0;
}

map <pair <vector <pair <int, int> >, pair <int, int> >, pair <pair <int, int>, pair <int, int> > > P;

inline pair <pair <int, int>, pair <int, int> > solve(vector <pair <int, int> > vec) {
	int p1 = n, p2 = 1;
	for (auto p: vec) {
		p1 = min(p1, p.first);
		p2 = max(p2, p.first);
	}
	p1 = max(1, p1 - 1);
	p2 = min(p2 + 1, n);
	if (P.find(make_pair(vec, make_pair(n, m))) != P.end()) {
		return P[make_pair(vec, make_pair(n, m))];
	}
	int L1 = 1, R1 = 1, L2 = 1, R2 = 1;
	ld ans = 0;
	for (int l1 = p1; l1 <= p2; ++l1) {
		for (int r1 = l1; r1 <= p2; ++r1) {
			for (int l2 = 1; l2 <= m; ++l2) {
				for (int r2 = l2; r2 <= m; ++r2) {
					map <int, int> mp;
					for (auto p: vec) {
						if (p.first >= l1 && p.first <= r1 && p.second >= l2 && p.second <= r2) {
							++mp[r1 - l1 + r2 - l2 + 1];
						} else if (p.first >= l1 && p.first <= r1) {
							++mp[r2 - l2 + 1];
						} else if (p.second >= l2 && p.second <= r2) {
							++mp[r1 - l1 + 1];
						} else {
							++mp[0];
						}
					}
					ld res = 0;
					for (auto u: mp) {
						ld P = (ld)u.second / vec.size();
						res += -log(P) * P;
					}
					if (res > ans) {
						ans = res;
						L1 = l1, R1 = r1, L2 = l2, R2 = r2;
					}
				}
			}
		}
	}
	return P[make_pair(vec, make_pair(n, m))] = make_pair(make_pair(L1, R1), make_pair(L2, R2));
}

inline void solve() {
#ifdef LOCAL
	init();
#else
	cin >> n >> m;
#endif
	vector <pair <int, int> > vec;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			vec.emplace_back(make_pair(i, j));
		}
	}
	while (vec.size() > 1) {
		pair <pair <int, int>, pair <int, int> > p = solve(vec);
		int l1 = p.first.first, r1 = p.first.second, l2 = p.second.first, r2 = p.second.second;
		int ans = ask(l1, r1, l2, r2);
		vector <pair <int, int> > tmp = vec;
		vec.clear();
		for (auto p: tmp) {
			int res = 0;
			if (p.first >= l1 && p.first <= r1 && p.second >= l2 && p.second <= r2) {
				res = r1 - l1 + r2 - l2 + 1;
			} else if (p.first >= l1 && p.first <= r1) {
				res = r2 - l2 + 1;
			} else if (p.second >= l2 && p.second <= r2) {
				res = r1 - l1 + 1;
			} else {
				res = 0;
			}
			if (res == ans) {
				vec.emplace_back(p);
			}
		}
	}
	print_ans(vec[0].first, vec[0].second);
}

int main() {
#ifdef LOCAL
	T = 15000;
#else
	cin >> T;
#endif
	while (T--) {
		solve();
	}
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3552kb

input:

2
6 6
4
4
0
7 5
2
3
2

output:

? 1 1 2 3
? 2 2 3 4
? 1 1 1 2
! 2 3
? 1 1 3 2
? 1 1 2 3
? 2 1 3 4
! 1 4

result:

ok Good (2 test cases)

Test #2:

score: 0
Accepted
time: 16ms
memory: 3700kb

input:

3
15 15
14
8
6
8
3 15
8
11
1
1
15 15
8
3
11
0

output:

? 1 1 7 8
? 1 5 4 9
? 1 1 2 6
? 2 1 3 7
! 2 7
? 1 1 2 8
? 2 1 3 11
? 1 1 1 13
? 1 1 1 12
! 2 12
? 1 1 7 8
? 1 1 3 11
? 3 1 5 9
? 3 1 4 1
! 5 9

result:

ok Good (3 test cases)

Test #3:

score: 0
Accepted
time: 135ms
memory: 3876kb

input:

100
6 6
2
2
0
3 4
2
1
7 8
4
0
0
5 6
0
0
0
9 4
4
4
0
11 4
5
2
2
3
15 12
7
3
4
2
5 9
2
4
0
6 7
3
0
4
9 9
8
2
4
0
11 4
5
2
2
3
12 7
4
0
0
0
14 7
0
4
0
1
9 6
0
3
1
12 11
6
0
2
0
3 14
7
10
1
1
15 12
0
13
3
0
7 10
8
0
0
15 5
0
0
4
0
11 9
4
8
5
0
14 7
4
7
1
15 10
0
5
8
0
7 4
3
3
0
5 13
6
9
1
0
13 8
0
4
3
0...

output:

? 1 1 2 3
? 2 1 4 2
? 2 1 3 1
! 4 3
? 1 1 2 3
? 2 1 2 1
! 3 1
? 1 1 3 4
? 1 1 2 6
? 2 1 2 7
! 3 8
? 1 1 2 3
? 2 1 3 4
? 3 1 4 5
! 5 6
? 1 1 4 2
? 4 2 6 3
? 4 1 5 1
! 6 2
? 1 1 5 2
? 5 2 8 3
? 5 1 6 2
? 6 1 7 2
! 7 1
? 1 1 7 6
? 7 1 11 3
? 7 1 9 4
? 7 1 8 5
! 9 5
? 1 1 2 4
? 2 3 3 5
? 2 1 2 3
! 3 4
?...

result:

ok Good (100 test cases)

Test #4:

score: 0
Accepted
time: 119ms
memory: 3760kb

input:

50
9 8
0
3
2
4 11
0
2
0
1
9 11
6
2
7
13 8
4
6
2
4 15
7
0
14
12
8 9
4
0
2
11 12
5
0
0
2
11 14
0
0
0
14
14 14
7
0
6
0
8 3
5
0
2
6 7
6
3
2
4 12
6
2
7
9
6 4
4
4
1
9 15
0
3
0
0
12 7
9
0
2
0
13 14
6
3
0
7
12 11
0
11
2
0
12 13
6
8
2
4
8 5
5
0
3
8 10
5
2
6
13 3
6
0
3
2
8 10
0
7
8
1
15 15
0
11
15
12
8 3
5
4
...

output:

? 1 1 5 4
? 5 1 7 6
? 7 1 8 5
! 9 5
? 1 1 2 5
? 2 1 3 8
? 3 1 3 6
? 3 1 3 7
! 4 7
? 1 1 4 6
? 1 1 2 8
? 2 1 3 7
! 3 8
? 1 1 6 4
? 1 1 3 6
? 1 1 2 7
! 3 7
? 1 1 2 7
? 2 1 3 11
? 1 1 2 13
? 1 1 2 12
! 1 13
? 1 1 4 5
? 4 1 6 2
? 6 1 7 3
! 8 3
? 1 1 5 6
? 5 1 8 3
? 8 1 9 4
? 9 1 10 5
! 11 5
? 1 1 5 7
? ...

result:

ok Good (50 test cases)

Test #5:

score: 0
Accepted
time: 103ms
memory: 3824kb

input:

50
9 14
4
0
2
3
15 4
8
2
2
6 6
3
4
1
10 11
10
4
0
10 3
5
0
2
3
12 13
12
6
4
0
5 15
2
0
2
1
15 9
10
3
3
0
11 7
4
2
0
1
3 8
5
2
4
7 7
6
0
1
12 9
4
8
6
1
3 5
3
0
5 3
4
0
10 12
6
2
0
2
7 3
2
0
0
11 11
6
11
8
0
15 8
10
0
2
0
11 11
0
8
2
1
7 14
7
11
0
9
9 8
4
6
8
7 6
6
0
2
6 6
2
3
3
15 4
8
2
2
9 11
0
4
7
...

output:

? 1 1 4 7
? 4 5 6 8
? 6 3 7 5
? 7 1 8 3
! 8 4
? 1 1 7 2
? 1 2 3 3
? 1 1 1 2
! 1 1
? 1 1 2 3
? 2 1 3 4
? 1 1 1 5
! 2 5
? 1 1 5 6
? 1 1 2 3
? 2 2 3 4
! 1 1
? 1 1 5 2
? 5 2 7 3
? 7 1 8 2
? 8 1 9 2
! 9 1
? 1 1 6 7
? 1 1 3 4
? 1 3 2 5
? 2 1 3 3
! 1 4
? 1 1 2 7
? 2 1 3 3
? 3 1 4 5
? 4 1 4 4
! 5 4
? 1 1 7 ...

result:

ok Good (50 test cases)

Test #6:

score: 0
Accepted
time: 66ms
memory: 3824kb

input:

50
14 14
8
14
0
11
6 3
0
0
0
13 6
0
8
2
1
11 13
7
3
8
1
9 4
5
4
0
10 12
6
2
0
0
3 12
0
0
0
1
12 5
0
3
4
13 4
7
2
1
2
9 9
0
0
8
10 6
0
0
5
3 5
3
4
6 12
8
0
0
0
7 9
0
3
2
10 11
5
3
4
0
8 5
5
3
1
5 4
3
0
7 5
3
4
0
13 4
7
4
0
1
5 14
2
3
0
1
4 13
6
0
11
13
5 13
2
2
3
10 5
0
6
4
9 8
0
3
0
4 12
2
4
1
5 7
2...

output:

? 1 1 7 8
? 1 1 4 11
? 1 1 2 9
? 2 1 3 10
! 3 10
? 1 1 3 2
? 3 1 4 1
? 4 1 5 1
! 6 3
? 1 1 6 3
? 6 1 9 5
? 6 1 7 4
? 7 1 8 1
! 8 4
? 1 1 6 7
? 1 1 3 10
? 3 1 4 8
? 3 1 3 9
! 4 9
? 1 1 4 2
? 1 2 2 4
? 1 1 1 1
! 2 2
? 1 1 5 6
? 1 1 2 9
? 2 1 3 7
? 3 1 4 8
! 5 9
? 1 1 2 6
? 2 1 2 9
? 2 1 2 10
? 2 1 2 1...

result:

ok Good (50 test cases)

Test #7:

score: 0
Accepted
time: 99ms
memory: 3848kb

input:

50
12 15
0
0
14
0
6 7
4
5
0
10 5
2
2
0
0
11 9
6
4
0
14 5
2
6
0
14 8
0
0
3
0
15 12
6
12
2
1
8 13
9
4
4
1
4 15
2
3
1
0
12 8
0
0
0
1
6 12
0
2
0
1
11 5
6
3
0
0
13 6
3
0
2
1
11 13
0
3
2
0
9 7
7
3
1
5 13
0
2
0
1
5 6
4
2
3
14 7
0
8
0
1
8 10
8
4
0
13 9
9
4
0
10 11
6
0
0
8 10
0
7
8
1
12 6
3
4
6
0
11 13
6
3
0...

output:

? 1 1 6 7
? 6 1 9 11
? 9 1 10 13
? 9 1 9 12
! 10 13
? 1 1 3 4
? 1 1 2 5
? 2 1 3 6
! 1 7
? 1 1 5 2
? 1 1 2 3
? 2 1 3 1
? 3 1 4 1
! 5 3
? 1 1 6 4
? 6 1 8 2
? 6 2 7 4
! 8 1
? 1 1 7 2
? 1 1 3 4
? 1 1 2 3
! 3 4
? 1 1 7 4
? 7 4 10 6
? 10 1 12 7
? 12 1 13 1
! 14 7
? 1 1 7 6
? 1 1 4 9
? 1 1 2 7
? 2 1 3 1
! ...

result:

ok Good (50 test cases)

Test #8:

score: 0
Accepted
time: 103ms
memory: 3760kb

input:

50
11 11
5
3
0
0
10 11
6
0
11
4 4
0
0
13 12
6
4
2
1
14 9
10
3
0
2
12 5
2
6
4
1
14 13
0
12
8
4 8
0
7
1
14 15
8
3
9
0
14 3
7
4
1
1
13 10
6
4
2
3
14 10
7
5
2
1
9 6
6
2
3
12 9
9
3
4
5 11
0
0
10
10 5
0
3
2
1
12 5
2
3
0
1
12 3
7
2
2
12 5
2
6
4
1
8 14
0
12
8
1
4 15
2
0
0
1
10 6
7
4
2
9 11
4
0
2
3
10 7
5
0
...

output:

? 1 1 5 6
? 5 1 8 3
? 5 1 6 4
? 6 1 7 5
! 8 6
? 1 1 5 6
? 1 1 3 9
? 3 1 4 10
! 4 10
? 1 1 2 3
? 2 1 3 1
! 4 4
? 1 1 7 6
? 1 1 4 9
? 4 1 5 7
? 5 1 6 1
! 6 7
? 1 1 7 4
? 1 1 3 2
? 3 2 5 3
? 5 1 6 2
! 7 1
? 1 1 6 2
? 1 1 3 4
? 1 1 2 3
? 1 1 1 1
! 1 3
? 1 1 7 6
? 7 1 10 9
? 7 1 8 7
! 8 7
? 1 1 2 4
? 2 1...

result:

ok Good (50 test cases)

Test #9:

score: 0
Accepted
time: 83ms
memory: 3704kb

input:

50
9 10
4
0
4
8 7
0
5
0
4 12
7
3
0
0
7 10
5
0
2
14 10
11
3
0
3
3 7
4
0
8 15
7
12
2
8
3 14
7
0
13
12
15 3
9
4
1
0
14 3
7
4
0
0
5 12
2
2
3
4 11
6
2
1
3
10 4
0
3
0
0
10 12
6
10
0
8
11 6
3
2
1
14 7
7
4
0
3
4 12
2
2
1
5 12
0
2
0
1
8 11
8
4
4
0
5 5
2
2
2
5 8
5
2
3
12 8
4
6
2
3 4
3
1
11 10
10
2
0
1
3 4
3
1...

output:

? 1 1 4 5
? 4 1 7 3
? 7 1 8 4
! 8 5
? 1 1 4 3
? 4 1 6 5
? 4 1 5 6
! 6 7
? 1 1 2 6
? 2 1 3 3
? 1 1 1 4
? 1 1 1 5
! 2 6
? 1 1 4 5
? 1 1 2 7
? 2 1 3 8
! 4 8
? 1 1 7 5
? 1 1 3 2
? 3 2 5 3
? 5 1 6 2
! 6 1
? 1 1 2 3
? 2 2 3 4
! 1 1
? 1 1 4 7
? 1 1 2 11
? 2 1 3 9
? 1 1 2 8
! 1 9
? 1 1 2 7
? 2 1 3 10
? 1 1 ...

result:

ok Good (50 test cases)

Test #10:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

16
3 3
1
1
3 3
2
1
3
3 3
1
1
3 3
0
1
3 3
2
2
3 3
2
1
2
3 3
1
2
2
3 3
1
0
3 3
0
0
3 4
4
4
1
3 4
4
4
0
4 3
4
4
1
4 3
4
4
0
4 3
4
0
4 4
4
4
1
4 4
0
0

output:

? 1 1 1 2
? 1 1 2 1
! 2 2
? 1 1 1 2
? 1 1 2 1
? 1 1 2 2
! 1 2
? 1 1 1 2
? 1 1 2 1
! 2 2
? 1 1 1 2
? 1 1 2 1
! 2 3
? 1 1 1 2
? 1 1 2 1
! 1 1
? 1 1 1 2
? 1 1 2 1
? 1 1 2 2
! 1 3
? 1 1 1 2
? 1 1 2 1
? 1 1 2 2
! 3 1
? 1 1 1 2
? 1 1 2 1
! 3 2
? 1 1 1 2
? 1 1 2 1
! 3 3
? 1 1 2 3
? 2 2 3 4
? 1 1 1 2
! 2 2
...

result:

ok Good (16 test cases)

Test #11:

score: 0
Accepted
time: 1064ms
memory: 4744kb

input:

15000
12 8
6
4
0
2
12 15
7
11
13
2
3 9
0
0
0
0
11 10
10
4
3
1
3 14
2
1
1
11 9
9
3
4
14 4
7
2
2
3
8 5
0
4
0
11 10
5
0
0
10
8 9
4
2
2
5 12
2
0
0
0
13 9
9
4
3
2
7 13
3
3
4
0
12 12
5
0
0
6
15 9
4
3
3
1
12 12
6
0
2
0
9 10
5
8
6
9 15
7
2
2
0
12 14
12
0
0
2
5 4
0
4
15 9
4
6
0
0
14 7
7
5
2
1
8 15
4
0
0
1
14...

output:

? 1 1 6 4
? 6 1 9 2
? 9 2 10 4
? 10 1 11 2
! 12 1
? 1 1 6 7
? 1 1 3 11
? 1 1 2 13
? 2 1 3 14
! 1 14
? 1 1 2 4
? 2 1 2 6
? 2 1 2 7
? 2 1 2 8
! 3 9
? 1 1 6 5
? 1 1 3 2
? 1 2 2 4
? 1 1 1 2
! 2 1
? 1 1 2 7
? 2 1 2 3
? 2 1 2 1
! 3 1
? 1 1 6 4
? 1 1 3 2
? 3 2 4 4
! 4 2
? 1 1 7 2
? 7 2 10 3
? 7 1 8 2
? 8 1...

result:

ok Good (15000 test cases)
English 繁體中文 简体中文

服务器时间: 2025-02-01 22:41:42 | 开源项目