QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743309#9432. PermutationKellyWLJRE 0ms3840kbC++172.5kb2024-11-13 18:54:282024-11-13 18:54:29

Judging History

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

  • [2024-11-13 18:54:29]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3840kb
  • [2024-11-13 18:54:28]
  • 提交

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));
    static int T = 0;   ++T;
    assert(T <= 6666);
    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 || p.empty())  return;
    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: 3840kb

input:

5
2
1
1
2
1
0
0

output:

0 3 3 5 5 5 
0 1 1 2 2 2 
0 5 5 1 1 1 
0 3 4 3 3 3 
0 5 5 1 1 2 
0 5 5 5 5 1 
0 1 1 1 2 1 
1 3 4 2 1 5 

result:

ok Accepted

Test #2:

score: -100
Runtime Error

input:

1000
1
1
1
2
1
1
1
1
0
0
1
0
1
2
2
1
2
1
1
0
2
1
0
1
1
2
2
1
2
1
2
1
1
1
1
0
2
1
1
1
1
1
1
0
2
0
2
1
2
1
0
2
0
1
1
1
1
0
1
2
1
0
0
0
1
1
1
1
1
2
1
1
1
0
1
1
0
0
1
0
0
0
2
1
2
1
2
1
0
2
1
0
1
2
1
2
0
1
2
0
2
1
0
1
1
0
1
0
1
2
2
1
2
1
0
1
1
2
0
1
1
0
1
1
0
2
1
1
2
1
0
2
1
0
1
1
2
2
0
1
2
0
1
0
1
1
2
1...

output:

0 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 28...

result: