QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509162#6345. Random Interactive Convex Hull BotMine_KingTL 0ms0kbC++141.5kb2024-08-08 11:25:072024-08-08 11:25:08

Judging History

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

  • [2024-08-08 11:25:08]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-08-08 11:25:07]
  • 提交

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);
	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;
		} 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 - 1, 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("! ");
	for (int i : vec) printf("%d ", i);
	puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

5

output:


result: