QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#741792 | #9432. Permutation | fanchuanyu | TL | 0ms | 0kb | C++14 | 1.2kb | 2024-11-13 15:13:58 | 2024-11-13 15:13:59 |
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