QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#742287#9432. PermutationKXGRE 0ms0kbC++143.3kb2024-11-13 16:17:342024-11-13 16:17:39

Judging History

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

  • [2024-11-13 16:17:39]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-13 16:17:34]
  • 提交

answer

#include <vector>
#include <cstdio>
#include <bits/extc++.h>
using namespace std;
typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> rbtree;
int n, ans[1010];
int query(vector<int> a) {
    printf("0 ");
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    fflush(stdout);
    int x;
    scanf("%d", &x);
    return x;
}
int fa[1010], dir[1010];
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    fa[find(x)] = find(y);
}
void solve(int l, int r, vector<int> S, int t) {
    if (l == r) {
        ans[l] = S[0];
        return;
    }
    int mid = (l + r) >> 1;
    rbtree now;
    for (int i : S) {
        now.insert(i);
        dir[i] = 0;
    }
    for (int i = l; i <= r; i++) {
        fa[i] = i;
    }
    while (true) {
        if (now.size() < 2) break;
        int siz = now.size();
        int xid = rand() % siz, yid = rand() % siz;
        if (xid == yid) continue;
        auto xit = now.find_by_order(xid);
        auto yit = now.find_by_order(yid);
        int x = *xit, y = *yit;
        vector<int> que;
        for (int i = 1; i <= n; i++) {
            if (i < l || i > r) {
                que.push_back(t);
            } else if (i <= mid) {
                que.push_back(x);
            } else {
                que.push_back(y);
            }
        }
        int res = query(que);
        if (res == 0) {
            dir[x] = 1;
            dir[y] = -1;
            now.erase(xit);
            now.erase(yit);
        } else if (res == 2) {
            dir[x] = -1;
            dir[y] = 1;
            now.erase(xit);
            now.erase(yit);
        } else {
            merge(x, y);
            now.erase(xit);
        }
    }
    // printf("%d %d Ok %d\n", l, r, now.size());
    int left = 0, right = 0;
    for (int i : S) {
        if (dir[i] == -1) {
            left = i;
        }
        if (dir[i] == 1) {
            right = i;
        }
    }
    if (now.size() == 1) {
        int x = *now.begin();
        if (left == 0) {
            dir[x] = -1;
        } else if (right == 0) {
            dir[x] = 1;
        } else {
            vector<int> que;
            for (int i = 1; i <= n; i++) {
                if (i < l || i > r) {
                    que.push_back(t);
                } else if (i <= mid) {
                    que.push_back(x);
                } else {
                    que.push_back(left);
                }
            }
            int res = query(que);
            if (res == 0) {
                dir[x] = 1;
            } else {
                dir[x] = -1;
            }
        }
    }
    vector<int> ls, rs;
    for (int i : S) {
        dir[i] = dir[find(i)];
        if (dir[i] == -1) {
            ls.push_back(i);
        } else {
            rs.push_back(i);
        }
    }
    solve(l, mid, ls, ls.front());
    solve(mid + 1, r, rs, rs.front());
}
int main() {
    scanf("%d", &n);
    vector<int> S;
    for (int i = 1; i <= n; i++) {
        S.push_back(i);
    }
    solve(1, n, S, 0);
    printf("1 ");
    for (int i = 1; i <= n; i++) {
        printf("%d ", ans[i]);
    }
    fflush(stdout);
    return 0;
}

详细

Test #1:

score: 0
Runtime Error

input:

5
1
2
0
1
2
1
2

output:

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

result: