QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#741792#9432. PermutationfanchuanyuTL 0ms0kbC++141.2kb2024-11-13 15:13:582024-11-13 15:13:59

Judging History

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

  • [2024-11-13 15:13:59]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-11-13 15:13:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int ans[100005];
int n;

int check(int mid, int x, int y) {
	for (int i = 1; i <= mid; i++)
		cout << x << ' ';
	for (int i = mid + 1; i <= n; i++)
		cout << y << ' ';
	cout << '\n';
	int a;
	cin >> a;
	return a;
}

void dfs(int l, int r, vector<int>ve) {
	if (l == r) {
		ans[l] = ve[0];
		return ;
	}
	int mid = l + r >> 1;
	random_shuffle(ve.begin(), ve.end());
	vector<int>nums[2];
	int L = 0, pos = 0;
	while (pos + 1 < ve.size()) {
		int num = check(mid, ve[pos], ve[pos + 1]);
		if (num == 0 || num == 2) {
			int tp = (2 - num) / 2;
			for (int i = L; i <= pos; i++)
				nums[tp].push_back(ve[i]);
			nums[tp ^ 1].push_back(ve[pos + 1]);
			L = pos = pos + 2;
		} else {
			pos++;
		}
	}
	if (nums[0].size() != mid - l + 1) {
		for (int i = L; i < ve.size(); i++) {
			nums[0].push_back(ve[i]);
		}
	} else {
		for (int i = L; i < ve.size(); i++) {
			nums[1].push_back(ve[i]);
		}
	}
	dfs(l, mid, nums[0]);
	dfs(mid + 1, r, nums[1]);
}

int main() {
	srand(time(NULL));
	cin >> n;
	vector<int>ve;
	for (int i = 1; i <= n; i++) {
		ve.push_back(i);
	}
	dfs(1, n, ve);
	cout << 1;
	for (int i = 1; i <= n; i++)
		cout << ' ' << ans[i];
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

5

output:

1 1 1 3 3 

result: