QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309596#7535. Limited Shuffle Restoring8BQubeWA 4ms3972kbC++203.3kb2024-01-20 18:53:002024-01-20 18:53:00

Judging History

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

  • [2024-01-20 18:53:00]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3972kb
  • [2024-01-20 18:53:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

vector<vector<int>> pool;
map<vector<int>, pii> decision;
map<vector<int>, int> step;

int get_decision(const vector<int> &q) {
    if (SZ(q) == 1) return 0;
    if (decision.find(q) != decision.end())
        return step[q];
    int ans = 100;
    for (int i = 0; i < 5; ++i)
        for (int j = i + 1; j < 5; ++j) {
            if (SZ(q) == SZ(pool) && (i != 3 || j != 4)) {
                continue;
            }
            vector<int> lft, rgt;
            for (int k : q)
                if (pool[k][i] < pool[k][j])
                    lft.pb(k);
                else
                    rgt.pb(k);
            if (lft.empty() || rgt.empty()) continue;
            int lval = get_decision(lft);
            int rval = get_decision(rgt);
            if (ans > max(lval, rval) + 1) {
                ans = max(lval, rval) + 1;
                decision[q] = pii(i, j);
            }
        }
    return step[q] = ans;
}

map<pii, int> mem;

int cmp(int l, int r) {
    int flag = 0;
    if (l > r) swap(l, r), flag = 1;
    if (mem.find(pii(l, r)) != mem.end())
        return mem[pii(l, r)] ^ flag;
    cout << "? " << l << " " << r << endl;
    char c;
    cin >> c;
    return (mem[pii(l, r)] = int(c == '<')) ^ flag;
}

int pos[10], ans[100005], pl[1000005];

vector<int> solve(vector<int> cur) {
    while (SZ(cur) > 1) {
        auto [l, r] = decision[cur];
        vector<int> nxt;
        int res = cmp(pos[l + 1], pos[r + 1]);
        for (int k : cur)
            if ((pool[k][l] < pool[k][r]) == res)
                nxt.pb(k);
        cur.swap(nxt);
    }
    return pool[cur[0]];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    vector<int> perm(5);
    iota(ALL(perm), 1);
    for (int i = 0; i <= 2; i++)
        for (int j = 1; j <= 3; j++)
            for (int k = 2; k <= 4; k++)
                for (int l = 3; l <= 4; l++) {
                    vector<int> tmp = perm;
                    swap(tmp[0], tmp[i]);
                    swap(tmp[1], tmp[j]);
                    swap(tmp[2], tmp[k]);
                    swap(tmp[3], tmp[l]);
                    pool.pb(tmp);
                }
    vector<int> all(SZ(pool));
    iota(ALL(all), 0);
    get_decision(all);
    int n, orgn;
    cin >> n, orgn = n;
    if (n == 1) return cout << "! 1\n", 0;
    pos[4] = n - 1, pos[5] = n;
    while (n >= 5) {
        for (int i = 1; i <= 3; ++i)
            pos[i] = n - 5 + i;
        auto res = solve(all);
        for (int i = 0; i < 5; ++i)
            cerr << res[i] << " \n"[i == 4];
        for (int i = 0; i < 5; ++i)
           ans[res[i]] = pos[i + 1];
        pos[4] = ans[n - 4], pos[5] = ans[n - 3];
        n -= 3;
    }
    vector<int> idx;
    for (int i = 1; i <= n - 2; ++i)
        idx.pb(i);
    idx.pb(pos[4]), idx.pb(pos[5]);
    sort(ALL(idx), cmp);
    for (int i = 0; i < SZ(idx); ++i)
        ans[i + 1] = idx[i];
    for (int i = 1; i <= orgn; ++i)
        pl[ans[i]] = i;
    cout << "!";
    for (int i = 1; i <= orgn; ++i)
        cout << " " << pl[i];
    cout << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3972kb

input:

5
>
<
<
>
<
<

output:

? 4 5
? 1 5
? 3 5
? 1 3
? 1 2
? 2 5
! 2 3 1 5 4

result:

ok yeah, seems ok, spent 6 queries of 13

Test #2:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

1

output:

! 1

result:

ok yeah, seems ok, spent 0 queries of 6

Test #3:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

2
>

output:

? 1 2
! 2 1

result:

ok yeah, seems ok, spent 1 queries of 8

Test #4:

score: 0
Accepted
time: 4ms
memory: 3788kb

input:

3
>
<
>

output:

? 1 2
? 2 3
? 1 3
! 3 1 2

result:

ok yeah, seems ok, spent 3 queries of 10

Test #5:

score: 0
Accepted
time: 4ms
memory: 3764kb

input:

4
<
<
>
<
>
>

output:

? 1 2
? 1 3
? 2 3
? 1 4
? 2 4
? 3 4
! 1 4 3 2

result:

ok yeah, seems ok, spent 6 queries of 11

Test #6:

score: 0
Accepted
time: 4ms
memory: 3948kb

input:

5
>
<
>
>
>
>

output:

? 4 5
? 1 5
? 3 5
? 2 5
? 3 4
? 2 4
! 1 4 5 3 2

result:

ok yeah, seems ok, spent 6 queries of 13

Test #7:

score: -100
Wrong Answer
time: 4ms
memory: 3784kb

input:

6
>
<
>
>
>
>
<
<

output:

? 5 6
? 2 6
? 4 6
? 3 6
? 4 5
? 3 5
? 1 6
? 1 5
! 1 0 4 5 3 2

result:

wrong answer Integer element [index=2] equals to 0, violates the range [1, 6]