QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#745820 | #9432. Permutation | chroneZ | WA | 1ms | 3608kb | C++17 | 2.2kb | 2024-11-14 11:47:09 | 2024-11-14 11:47:10 |
Judging History
answer
// Such a destiny was not desired.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 1e3 + 5;
int n, p[N];
inline int ask(int m, int x, int y) {
cout << 0 << " ";
for(int i = 1; i <= m; i++) cout << x << " ";
for(int i = m + 1; i <= n; i++) cout << y << " ";
cout << endl;
int ret; cin >> ret;
return ret;
}
struct DUS {
int f[N];
inline void init(int n) {iota(f + 1, f + n + 1, 1);}
inline int find(int x) {while(x != f[x]) x = f[x] = f[f[x]]; return x;}
inline void merge(int x, int y) {
x = find(x), y = find(y);
f[y] = x;
}
} D;
int g[N];
void solve(int l, int r, vector<int> S) {
assert(S.size() == r - l + 1);
if(l == r) return p[l] = S[0], void();
int m = l + r >> 1;
vector<int> o = S;
vector<int> L, R;
while(S.size() > 1) {
int itx = rng() % S.size(), ity = rng() % S.size();
while(itx == ity) itx = rng() % S.size(), ity = rng() % S.size();
int x = S[itx], y = S[ity];
int e = ask(m, x, y);
if(e == 0) {
g[x] = 1, g[y] = 0;
if(itx < ity) swap(itx, ity);
S.erase(S.begin() + itx), S.erase(S.begin() + ity);
} else if(e == 2) {
g[x] = 0, g[y] = 1;
if(itx < ity) swap(itx, ity);
S.erase(S.begin() + itx), S.erase(S.begin() + ity);
} else {
D.merge(x, y);
S.erase(S.begin() + ity);
}
}
if(S.size() == 1) {
int x = -1;
for(auto y : o) {
if(y != S[0]) {
x = y;
break;
}
}
int e = ask(m, S[0], x);
if(e == 0) g[S[0]] = 1;
else if(e == 2) g[S[0]] = 0;
else D.merge(x, S[0]);
}
for(auto x : o) {
g[x] = g[D.find(x)];
if(g[x] == 0) L.push_back(x);
else R.push_back(x);
}
for(auto x : o) {
D.f[x] = x;
}
assert(L.size() == m - l + 1);
assert(R.size() == r - m);
// solve(l, m, L);
// solve(m + 1, r, R);
}
int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
vector<int> U(n);
iota(U.begin(), U.end(), 1);
D.init(n);
solve(1, n, U);
cout << 1 << " ";
for(int i = 1; i <= n; i++) cout << p[i] << " ";
cout << endl;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3608kb
input:
5 1 0 0
output:
0 2 2 2 3 3 0 1 1 1 4 4 0 5 5 5 2 2 1 0 0 0 0 0
result:
wrong answer Integer element [index=1] equals to 0, violates the range [1, 5]