QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743228#9432. PermutationKellyWLJRE 0ms3616kbC++172.4kb2024-11-13 18:38:072024-11-13 18:38:16

Judging History

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

  • [2024-11-13 18:38:16]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3616kb
  • [2024-11-13 18:38:07]
  • 提交

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...

result: