QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#509177	#6345. Random Interactive Convex Hull Bot	Mine_King	AC ✓	56ms	4048kb	C++14	1.6kb	2024-08-08 11:32:43	2024-08-08 11:32:44

Judging History

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

[2024-08-08 11:32:44]
评测

测评结果：AC
用时：56ms
内存：4048kb

查看

[2024-08-08 11:32:43]
提交

answer

// 長い夜の終わりを信じながら
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n;
vector<int> vec({1, 2, 3});

int query(int a, int b, int c) {
	printf("? %d %d %d\n", a, b, c), fflush(stdout);
	int x;
	scanf("%d", &x);
	return x;
}

int main() {
	scanf("%d", &n);
	if (query(1, 2, 3) == -1) swap(vec[1], vec[2]);
	for (int i = 4; i <= n; i++) {
		int m = vec.size();
		int type = query(vec[0], vec[m / 2], i);
		int le, ri;
		if (type == 1) {
			int l = m / 2, r = m - 1;
			while (l < r) {
				int mid = (l + r) / 2 + 1;
				if (query(vec[0], vec[mid], i) == 1) l = mid;
				else r = mid - 1;
			}
			le = l, ri = (l + 1) % m;
		} else {
			int l = 1, r = m / 2;
			while (l < r) {
				int mid = (l + r) / 2;
				if (query(vec[0], vec[mid], i) == -1) r = mid;
				else l = mid + 1;
			}
			le = (r + m - 1) % m, ri = r;
		}
		if (query(vec[le], vec[ri], i) == 1) continue;
		while (query(vec[(le + m - 1) % m], vec[le], i) == -1) le = (le + m - 1) % m;
		while (query(vec[(ri + 1) % m], vec[ri], i) == 1) ri = (ri + 1) % m;
		vector<int> tmp({i});
		for (int j = ri; j != le; j = (j + 1) % m) tmp.push_back(vec[j]);
		tmp.push_back(vec[le]);
		vec.swap(tmp);
	}
	printf("! %d ", (int)vec.size());
	for (int i : vec) printf("%d ", i);
	puts(""), fflush(stdout);
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3724kb

input:

5
-1
-1
-1
1
1
-1
-1
-1
1
-1

output:

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

result:

ok OK, 10 queries, 4 point in hull

Test #2:

score: 0

Accepted

time: 3ms

memory: 3764kb

input:

50
-1
1
1
-1
1
-1
1
-1
-1
1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
1
-1
-1
-1
1
-1
1
1
-1
-1
1
-1
1
-1
1
-1
-1
1
1
-1
-1
1
1
-1
-1
-1
1
-1
-1
1
1
-1
-1
1
1
1
-1
1
-1
1
1
1
-1
-1
1
-1
-1
1
-1
1
-1
1
-1
1
1
1
1
-1
1
1
-1
1
1
1
-1
1
-1
1
-1
-1
-1
1
1
-1
1
1
1
1
1
1
-1
-1
-1
1
-1
1
1
-1
-1
-1
1
-1
1
-1
-1
1
1
-1
-...

output:

result:

ok OK, 238 queries, 10 point in hull

Test #3:

score: 0

Accepted

time: 0ms

memory: 3768kb

input:

1000
-1
1
1
-1
1
-1
-1
-1
-1
-1
1
-1
1
1
-1
1
1
-1
1
1
-1
1
-1
1
-1
1
1
-1
-1
-1
-1
1
-1
1
1
-1
1
-1
-1
-1
1
-1
1
-1
1
-1
-1
1
1
-1
-1
1
-1
1
1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
1
1
-1
-1
1
-1
1
-1
-1
-1
-1
1
-1
-1
1
-1
1
-1
1
1
1
-1
-1
1
1
-1
-1
-1
-1
-1
1
-1
-1
1
1
1
1
-1
-1
1
-1
1
...

output:

result:

ok OK, 5155 queries, 21 point in hull

Test #4:

score: 0

Accepted

time: 12ms

memory: 3800kb

input:

output:

result:

ok OK, 10662 queries, 23 point in hull

Test #5:

score: 0

Accepted

time: 16ms

memory: 4036kb

input:

3000
1
-1
-1
1
-1
-1
-1
-1
1
1
-1
-1
1
-1
1
1
-1
1
1
-1
1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
1
1
1
-1
1
1
-1
-1
1
-1
1
1
-1
1
-1
1
-1
1
-1
-1
1
1
1
1
-1
-1
1
1
-1
-1
-1
1
-1
-1
1
1
1
-1
-1
-1
-1
1
1
-1
-1
1
-1
-1
1
-1
-1
-1
1
1
-1
-1
-1
1
-1
1
1
-1
-1
-1
-1
1
-1
1
-1
1
1
-1
-1
1
-1
-1...

output:

result:

ok OK, 15859 queries, 25 point in hull

Test #6:

score: 0

Accepted

time: 41ms

memory: 3796kb

input:

output:

result:

ok OK, 21471 queries, 22 point in hull

Test #7:

score: 0

Accepted

time: 27ms

memory: 4008kb

input:

4999
-1
-1
-1
1
-1
1
1
-1
1
1
-1
1
1
-1
1
-1
-1
1
1
1
-1
-1
1
1
1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
1
1
1
-1
-1
1
-1
1
-1
-1
1
-1
-1
-1
1
1
1
-1
1
1
-1
1
1
1
1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
1
1
1
-1
1
1
-1
1
1
-1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
1
-1
-1
-1
1
-1
1
-1
-1
1
1
-1...

output:

result:

ok OK, 27603 queries, 24 point in hull

Test #8:

score: 0

Accepted

time: 30ms

memory: 3772kb

input:

5000
-1
1
1
-1
1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
1
1
-1
-1
-1
-1
1
1
-1
1
-1
1
1
-1
-1
-1
1
1
-1
1
-1
-1
1
1
-1
-1
1
1
-1
1
1
1
-1
-1
1
1
-1
1
1
1
-1
1
1
-1
-1
-1
1
-1
1
-1
-1
-1
1
-1
1
1
-1
-1
-1
1
-1
-1
1
1
1
-1
1
1
-1
-1
1
-1
1
-1
-1
1
1
1
-1
1
1
1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
1
-1
1
1
1
1
-1
1
1
-1
1...

output:

result:

ok OK, 27145 queries, 21 point in hull

Test #9:

score: 0

Accepted

time: 28ms

memory: 3864kb

input:

5000
1
-1
-1
1
-1
1
1
-1
-1
-1
1
-1
1
-1
1
-1
-1
1
-1
1
-1
-1
1
-1
-1
-1
-1
1
1
-1
1
-1
-1
-1
1
-1
1
1
-1
-1
1
1
-1
1
-1
-1
1
1
1
-1
1
-1
1
1
-1
1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
1
-1
1
1
-1
-1
1
-1
-1
-1
1
1
-1
1
-1
-1
1
1
1
-1
-1
1
-1
-1
1
-1
1
-1
1
-1
1
1
-1
1
1
1
1
1
-1
1
-1
-1
1
-1
...

output:

result:

ok OK, 26985 queries, 27 point in hull

Test #10:

score: 0

Accepted

time: 21ms

memory: 4048kb

input:

output:

result:

ok OK, 27952 queries, 25 point in hull

Test #11:

score: 0

Accepted

time: 22ms

memory: 3716kb

input:

5000
1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
1
-1
1
-1
1
1
1
-1
1
-1
1
-1
1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
1
1
-1
-1
1
-1
1
-1
1
-1
1
1
1
-1
-1
1
1
-1
1
1
1
-1
1
1
1
-1
1
1
1
-1
1
1
1
-1
1
1
-1
-1
-1
-1
1
1
-1
-1
1
1
1
-1
-1
1
1
1
1
-1
1
-1
1
-1
-1
1
1
1
1
-1
-1
1
1
-1
1
-1
-1
-1
-1
1
-1
1
-1
-1
1
1...

output:

result:

ok OK, 27431 queries, 25 point in hull

Test #12:

score: 0

Accepted

time: 39ms

memory: 3856kb

input:

output:

result:

ok OK, 27534 queries, 27 point in hull

Test #13:

score: 0

Accepted

time: 35ms

memory: 3856kb

input:

5000
1
-1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
-1
-1
1
-1
1
1
-1
-1
1
-1
1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
1
1
-1
1
-1
1
1
-1
-1
-1
-1
-1
1
-1
1
1
-1
1
1
-1
1
1
1
1
-1
1
-1
1
1
1
1
-1
1
1
-1
1
-1
1
1
-1
1
-1
1
-1
-1
1
-1
1
-1
-1
1
1
-1
-1
1
1
-1
-1
1
1
-1
-1
1
1
-1
1
-1
1
-1
1
-1
-1
1
1
-1
...

output:

result:

ok OK, 28054 queries, 25 point in hull

Test #14:

score: 0

Accepted

time: 40ms

memory: 4044kb

input:

5000
-1
-1
-1
1
-1
-1
1
1
1
-1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
-1
1
-1
1
-1
-1
1
1
-1
-1
-1
-1
1
-1
1
1
1
-1
1
-1
-1
1
1
1
-1
1
1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
1
1
1
1
1
-1
1
1
-1
-1
1
1
1
-1
-1
1
-1
1
-1
-1
1
-1
1
-1
1
-1
1
1
-1
1
-1
-1
1
-1
1
1
1
-1
-1
-1
1
-1
-...

output:

result:

ok OK, 27579 queries, 28 point in hull

Test #15:

score: 0

Accepted

time: 52ms

memory: 3764kb

input:

output:

result:

ok OK, 27130 queries, 23 point in hull

Test #16:

score: 0

Accepted

time: 13ms

memory: 4036kb

input:

5000
-1
1
-1
-1
1
-1
1
-1
-1
1
-1
1
-1
-1
-1
1
-1
1
1
-1
1
1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
1
1
-1
1
-1
1
1
1
-1
-1
-1
1
1
-1
-1
-1
1
1
-1
-1
1
1
-1
-1
1
1
-1
-1
1
1
-1
-1
1
1
-1
-1
1
1
1
1
-1
-1
1
-1
-1
1
1
-1
1
-1
1
-1
-1
-1
-1
-1
1
-1
1
-1
1
1
-1
-1
1
-1
1
1
1
-1
-1
1
-1
1
1
-1
1
-1
-1
1
1
-1
...

output:

result:

ok OK, 27053 queries, 19 point in hull

Test #17:

score: 0

Accepted

time: 24ms

memory: 4036kb

input:

output:

result:

ok OK, 27277 queries, 25 point in hull

Test #18:

score: 0

Accepted

time: 35ms

memory: 3788kb

input:

5000
-1
1
-1
-1
1
-1
1
1
-1
1
1
-1
1
1
-1
-1
1
-1
-1
1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
-1
1
-1
-1
-1
-1
-1
1
1
-1
1
-1
-1
-1
1
-1
-1
-1
1
-1
1
1
-1
1
-1
1
-1
-1
1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
-1
-1
1
-1
1
1
-1
-1
1
-1
1
-1
-1
1
1
1
-1
-1
-1
-1
1
1
-1
-1
1
1
1
-1
1
-1
-1
1
-1
1
...

output:

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

result:

ok OK, 27466 queries, 24 point in hull

Test #19:

score: 0

Accepted

time: 31ms

memory: 3864kb

input:

5000
-1
1
1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
1
-1
-1
1
-1
-1
1
-1
1
-1
-1
-1
1
-1
-1
-1
-1
1
1
-1
-1
1
-1
-1
1
1
-1
-1
1
-1
1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
1
1
-1
-1
1
-1
1
1
1
-1
1
1
-1
1
1
-1
1
-1
...

output:

result:

ok OK, 27031 queries, 23 point in hull

Test #20:

score: 0

Accepted

time: 26ms

memory: 3796kb

input:

5000
-1
-1
-1
1
1
-1
1
1
-1
1
-1
1
1
-1
1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
1
-1
1
-1
1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
1
1
1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
1
1
-1
1
-1
1
-1
1
-1
1
1
-1
-1
1
1
1
-1
-1
1
1
1
1
-1
1
-1
1
-1
-1
1
-1
1
1
1
-1
1
1
1
-1
1
1
1
-1
1
-1
1
-1
-1
-1
-1
1
-1
1
-1
-1
1
1
-1
-1
1
1
1
-...

output:

result:

ok OK, 25252 queries, 19 point in hull

Test #21:

score: 0

Accepted

time: 56ms

memory: 3816kb

input:

5000
1
1
-1
-1
1
-1
1
1
-1
1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
1
1
-1
1
-1
1
-1
1
-1
-1
-1
1
-1
1
1
-1
1
1
-1
-1
-1
1
-1
-1
1
-1
1
-1
1
-1
1
-1
-1
-1
1
-1
1
-1
1
1
1
-1
1
1
1
1
-1
1
-1
1
1
-1
1
1
-1
1
-1
-1
1
-1
1
1
1
1
-1
1
-1
-1
1
1
1
-1
1
-1
-1
1
-1
1
-1
-1
1
1
-1
1
1
1
1
-1
-1
1
...

output:

result:

ok OK, 25828 queries, 20 point in hull

Test #22:

score: 0

Accepted

time: 49ms

memory: 3796kb

input:

5000
1
1
1
-1
1
-1
1
-1
1
-1
1
1
1
-1
-1
1
-1
1
-1
1
1
1
1
-1
1
-1
1
1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
1
-1
1
-1
1
-1
-1
1
1
-1
-1
1
1
1
-1
-1
1
-1
1
1
-1
1
1
1
-1
-1
-1
1
-1
1
1
1
-1
-1
1
-1
1
1
-1
1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
1
-1
1
1
-1
1
1
-1
1
-1
-1
1
-1
...

output:

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

result:

ok OK, 26940 queries, 24 point in hull

Test #23:

score: 0

Accepted

time: 44ms

memory: 3752kb

input:

5000
1
1
-1
1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
-1
-1
-1
-1
1
1
-1
1
-1
-1
-1
1
1
-1
1
-1
-1
1
1
-1
-1
-1
-1
1
-1
1
1
-1
1
-1
-1
1
1
-1
-1
1
1
-1
1
1
-1
-1
1
1
-1
-1
1
1
1
-1
1
-1
-1
-1
1
-1
-1
1
-1
1
1
-1
1
-1
-1
1
-1
1
1
1
-1
-1
-1
1
-1
-1
1
1
-1
1
1
1
-1
1
1
1
-1
1
1
1
-1
1
1
-1
1
1
1
-1
1
1
...

output:

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

result:

ok OK, 26471 queries, 21 point in hull