QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#743228 | #9432. Permutation | KellyWLJ | RE | 0ms | 3616kb | C++17 | 2.4kb | 2024-11-13 18:38:07 | 2024-11-13 18:38:16 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N = 1010; using pii = pair<int, int>;
mt19937 rnd(std::chrono::steady_clock().now().time_since_epoch().count());
int n, vis[N], b[N], a[N], p[N];
int ask(int x, int y, int els, int l, int mid, int r) {
memset(p, 0, sizeof(p));
for(int i = l; i <= mid; ++i) p[i] = x;
for(int i = mid + 1; i <= r; ++i) p[i] = y;
for(int i = 1; i <= n; ++i) if(!p[i]) p[i] = els;
cout << "0 ";
for(int i = 1; i <= n; ++i) cout << p[i] << " ";
cout << endl; int res = 0;
#ifdef Kelly
for(int i = 1; i <= n; ++i) res += p[i] == b[i];
return res;
#endif
cin >> res; return res;
}
void solve(int l, int r, vector<int> p) {
if(l == r) return void(a[l] = p[0]);
int mid = (l + r) >> 1;
if((r - l + 1) % 2 && (mid - l + 1) % 2) --mid;
else if((mid - l + 1) % 2 == 0 && (r - mid) % 2 == 0) ++mid;
vector<int> tmpl, tmpr; vector<pii> lsh;
int nw = p[0];
auto del = [&](int x) -> void {swap(p[x], p.back()), p.pop_back();};
// cerr << l << " " << r << " " << mid << "\n";
// for(int x : p) cerr << x << " ";
// cerr << "\n";
while(p.size() > 1) {
int x = rnd() % p.size(), y = rnd() % p.size();
while(y == x) y = rnd() % p.size();
if(x > y) swap(x, y);
int sum = ask(p[x], p[y], nw, l, mid, r);
if(sum == 0) tmpl.pb(p[y]), tmpr.pb(p[x]);
else if(sum == 2) tmpl.pb(p[x]), tmpr.pb(p[y]);
else lsh.pb({p[x], p[y]});
del(y), del(x);
}
if(tmpr.empty() && p.size()) nw = p[0];
for(auto [x, y] : lsh) {
int res = ask(tmpr.size() ? tmpr[0] : nw, x, nw, l, mid, r);
if(res == 0) tmpl.pb(x), tmpl.pb(y);
else tmpr.pb(x), tmpr.pb(y);
}
if(p.size()) tmpl.size() != mid - l + 1 ? tmpl.pb(p[0]) : tmpr.pb(p[0]);
solve(l, mid, tmpl), solve(mid + 1, r, tmpr);
}
int main() {
#ifdef Kelly
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
freopen("err.txt", "w", stderr);
#endif
cin >> n;
#ifdef Kelly
for(int i = 1; i <= n; ++i) cin >> b[i];
#endif
vector<int> tmp;
for(int i = 1; i <= n; ++i) tmp.pb(i);
solve(1, n, tmp);
cout << "1 ";
for(int i = 1; i <= n; ++i) cout << a[i] << " ";
cout << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
5 2 0 2 0 2
output:
0 3 3 5 5 5 0 2 2 4 4 4 0 3 4 3 3 3 0 5 5 5 5 2 0 2 2 2 1 2 1 3 4 2 1 5
result:
ok Accepted
Test #2:
score: -100
Runtime Error
input:
1000 2 1 2 0 2 2 2 1 1 1 1 2 1 1 2 2 0 0 1 1 0 2 1 2 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 2 2 1 2 0 1 2 0 2 1 2 1 2 1 1 1 1 1 1 1 2 0 2 2 1 2 0 1 1 1 0 2 0 1 1 1 1 1 1 2 1 2 1 2 1 0 1 2 1 1 1 1 0 0 1 1 2 2 0 1 1 0 0 0 2 1 0 1 0 0 1 1 1 2 2 2 0 2 1 2 1 1 0 1 1 1 1 0 0 1 2 1 2 2 2 2 0 0 2 1 0 1 1 1 0 2...
output:
0 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 4...