QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#623609#7778. Turning PermutationfoyonaczyWA 0ms3768kbC++201.7kb2024-10-09 13:25:102024-10-09 13:25:11

Judging History

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

  • [2024-10-09 13:25:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3768kb
  • [2024-10-09 13:25:10]
  • 提交

answer

#include<bits/stdc++.h>

using i64 = long long;
constexpr int L = 0, R = 1;
i64 k, f[55][55][2];
int n;
int ans[55], p[55], tot;
bool solved = false;

i64 dfs(int pos, int prepos, int lr) {
    if (pos > n) return 1;
    if (~f[pos][prepos][lr])return f[pos][prepos][lr];
    i64 res = 0;
    if (p[pos]) {
        int tmp = 0;
        for (int i = 1; i <= p[pos]; i++)if (ans[i] <= pos)tmp++;
        res += dfs(pos + 1, tmp, lr);
        if (res > k)res = k + 1;
    } else {
        if ((lr ^ (pos % 2)) == L) {
            for (int i = tot + 1; i <= prepos; i++) {
                res += dfs(pos + 1, i, lr);
                if (res > k)res = k + 1;
            }
        } else {
            for (int i = prepos + 1; i <= pos; i++) {
                res += dfs(pos + 1, i, lr);
                if (res > k)res = k + 1;
            }
        }
    }
    f[pos][prepos][lr] = res;
    return res;
}

void GetAns(int pos) {
    tot++;
    if (pos > n) {
        solved = true;
        for (int i = 1; i <= n; i++)std::cout << ans[i] << " ";
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (p[i])continue;
        p[i] = tot;
        int tmp = tot == 1 ? i : ans[1];
        i64 res;
        memset(f, -1, sizeof(f));
        res = dfs(2, 1, tmp % 2);
        if (res >= k) {
            ans[pos] = i;
            GetAns(pos + 1);
            return;
        }
        k -= res;
        p[i] = 0;
    }
}

void solve() {
    memset(f, -1, sizeof(f));
    std::cin >> n >> k;
    GetAns(1);
    if (!solved)std::cout << "-1\n";
}

int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
    int CZY = 1;
    while (CZY--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2

output:

2 1 3 

result:

ok 3 number(s): "2 1 3"

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

4 6

output:

3 1 2 4 

result:

ok 4 number(s): "3 1 2 4"

Test #4:

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

3 1

output:

1 3 2 

result:

ok 3 number(s): "1 3 2"

Test #6:

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

input:

3 10

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

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

input:

3 52

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

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

input:

3 756

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

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

input:

3 7721

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

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

input:

5 1

output:

1 3 2 5 4 

result:

ok 5 number(s): "1 3 2 5 4"

Test #11:

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

input:

5 8

output:

2 4 1 3 5 

result:

ok 5 number(s): "2 4 1 3 5"

Test #12:

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

input:

5 85

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

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

input:

5 846

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

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

input:

5 6957

output:

-1

result:

ok 1 number(s): "-1"

Test #15:

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

input:

8 1

output:

1 3 2 5 4 7 6 8 

result:

ok 8 numbers

Test #16:

score: -100
Wrong Answer
time: 0ms
memory: 3632kb

input:

8 7

output:

-1

result:

wrong answer 1st numbers differ - expected: '1', found: '-1'