QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32689#2567. Hidden RookYaoBIG#AC ✓454ms3644kbC++203.1kb2022-05-22 23:26:482022-05-22 23:26:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-22 23:26:49]
  • 评测
  • 测评结果：AC
  • 用时：454ms
  • 内存：3644kb
查看
  • [2022-05-22 23:26:48]
  • 提交

answer

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

int unsafeAsk(int y0, int y1, int x0, int x1) {
	cout << "? " << y0 + 1 << ' ' << x0 + 1 << ' ' << y1 + 1 << ' ' << x1 + 1 << endl;
	int res;
	cin >> res;
	return res;
}

pair<int, int> ask(int y0, int y1, int x0, int x1) {
	int dy = y1 - y0 + 1;
	int dx = x1 - x0 + 1;
	assert(dx != dy);
	assert(dy != 1 && dx != 1);
	
	int res = unsafeAsk(y0, y1, x0, x1);
	if (res == dy) return {0, 1};
	else if (res == dx) return {1, 0};
	else if (res > 0) return {1, 1};
	else return {0, 0};
}

void answer(int y, int x) {
	cout << "! " << y + 1 << ' ' << x + 1 << endl;
}

void update(int& y0, int& y1, int& x0, int& x1, int qy0, int qy1, int qx0, int qx1) {
	auto ans = ask(qy0, qy1, qx0, qx1);
	
	if (ans.first) {
		y0 = max(y0, qy0);
		y1 = min(y1, qy1);
	} else {
		if (y0 < qy0) y1 = qy0 - 1;
		else y0 = qy1 + 1;
	}

	if (ans.second) {
		x0 = max(x0, qx0);
		x1 = min(x1, qx1);
	} else {
		if (x0 < qx0) x1 = qx0 - 1;
		else x0 = qx1 + 1;
	}
}

void solve() {
	int h, w;
	cin >> h >> w;

	// Query rectangle has equal height and width: problem
	// Query rectangle has width or height equal to 1: problem

	// If height AND width <= 4:
	//	Special case these
	// If height != width:
	//	Always ask either some prefix, or some suffix, both of length >= 2
	// If height == width:
	//	Always ask either some prefix, some suffix, or some prefix or suffix missing the first position

	int y0 = 0, y1 = h - 1;
	int x0 = 0, x1 = w - 1;
	if (h <= 4 && w <= 4) {
		for (int j = 0; j < 2; ++j) {
			int ym = (y0 + y1) / 2;
			int cou = unsafeAsk(y0, ym, 0, w - 1);
			if (cou == (ym - y0) + w) y1 = ym;
			else y0 = ym + 1;
		}
		for (int j = 0; j < 2; ++j) {
			int xm = (x0 + x1) / 2;
			int cou = unsafeAsk(0, h - 1, x0, xm);
			if (cou == (xm - x0) + h) x1 = xm;
			else x0 = xm + 1;
		}
	} else {
		while(y0 != y1 || x0 != x1) {
			int ym = (y1 + y0) / 2;
			int xm = (x1 + x0) / 2;

			vector<pair<int, int>> qy_opts, qx_opts;
			if (ym > 0) qy_opts.emplace_back(0, ym);
			if (y0 > 0 && ym > 1) qy_opts.emplace_back(1, ym);
			if (ym + 1 < h - 1) qy_opts.emplace_back(ym + 1, h - 1);
			if (ym + 2 < h - 1 && y1 < h - 1) qy_opts.emplace_back(ym + 1, h - 2);
			
			if (xm > 0) qx_opts.emplace_back(0, xm);
			if (x0 > 0 && xm > 1) qx_opts.emplace_back(1, xm);
			if (xm + 1 < w - 1) qx_opts.emplace_back(xm + 1, w - 1);
			if (xm + 2 < w - 1 && x1 < w - 1) qx_opts.emplace_back(xm + 1, w - 2);
			
			if (y0 == 0 && y1 == h - 1 && x0 == 0 && x1 == w - 1 && h == w) {
				qy_opts.emplace_back(0, ym + 1);
			}

			bool found = 0;
			for (auto qy : qy_opts) {
				for (auto qx : qx_opts) {
					if (qy.second - qy.first != qx.second - qx.first) {
						update(y0, y1, x0, x1, qy.first, qy.second, qx.first, qx.second);
						found = 1;
					}
					if (found) break;
				}
				if (found) break;
			}
		}
	}
	answer(y0, x0);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	for (int ti = 0; ti < t; ++ti) solve();
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 3536kb

input:

2
6 6
6
5
7
7 5
3
5
6

output:

? 1 1 4 3
? 1 3 2 6
? 2 1 6 3
! 2 3
? 1 1 4 3
? 1 1 2 4
? 2 1 7 4
! 1 4

result:

ok Good (2 test cases)

Test #2:

score: 0
Accepted
time: 3ms
memory: 3484kb

input:

3
15 15
7
14
6
20
3 15
8
13
10
11
15 15
14
4
15
13

output:

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

result:

ok Good (3 test cases)

Test #3:

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

input:

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

output:

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

result:

ok Good (100 test cases)

Test #4:

score: 0
Accepted
time: 7ms
memory: 3500kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #5:

score: 0
Accepted
time: 8ms
memory: 3600kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #6:

score: 0
Accepted
time: 20ms
memory: 3644kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #7:

score: 0
Accepted
time: 11ms
memory: 3540kb

input:

50
12 15
0
0
24
22
6 7
4
6
5
10 5
7
0
4
11 9
6
11
9
0
14 5
3
6
2
6
14 8
0
0
13
15 12
6
12
2
9
8 13
10
5
8
13
4 15
2
4
8
7
12 8
0
0
7
10
6 12
0
5
13
7
11 5
6
9
10
13 6
3
4
4
8
11 13
0
9
10
18
9 7
8
4
6
6
5 13
0
4
13
12
5 6
2
4
4
14 7
0
16
13
8
8 10
8
4
7
0
13 9
11
6
0
8
10 11
6
0
0
8 10
0
8
13
12 6
3...

output:

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

result:

ok Good (50 test cases)

Test #8:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #9:

score: 0
Accepted
time: 3ms
memory: 3576kb

input:

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

output:

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

result:

ok Good (50 test cases)

Test #10:

score: 0
Accepted
time: 9ms
memory: 3584kb

input:

16
3 3
4
1
4
1
3 3
4
3
4
1
3 3
4
1
4
1
3 3
4
1
2
3
3 3
4
3
4
3
3 3
4
3
2
3
3 3
2
3
4
3
3 3
2
3
4
1
3 3
2
3
2
3
3 4
5
1
4
1
3 4
5
1
2
3
4 3
4
1
5
1
4 3
2
3
5
1
4 3
4
3
5
4
4 4
5
1
5
1
4 4
2
1
2
1

output:

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

result:

ok Good (16 test cases)

Test #11:

score: 0
Accepted
time: 454ms
memory: 3536kb

input:

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

output:

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

result:

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

服务器时间: 2025-02-01 23:54:43 | 开源项目