QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#280193#7778. Turning Permutationucup-team1631#WA 0ms3864kbC++202.9kb2023-12-09 14:21:482023-12-09 14:21:49

Judging History

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

  • [2023-12-09 14:21:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3864kb
  • [2023-12-09 14:21:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

#define all(A) A.begin(),A.end()
#define rep(i, n) for (ll i = 0; i < (ll) (n); i++)


ll gcd(ll(a), ll(b)) {
    if (a == 0)return b;
    if (b == 0)return a;
    ll c = a;
    while (a % b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return b;
}


vll F = { 1,1,2,4,10,32,122,544,2770,15872,101042,707584,
 5405530,44736512,398721962,3807514624,38783024290,
 419730685952,4809759350882,58177770225664,
 740742376475050,9902996106248192,
 138697748786275802,2030847773013704704 };

vector<bool> US;

ll multinom(vll& A) {
    ll N = A.size();
    ll S = 0;
    rep(i, N)S += A[i];
    ll res = 1;
    rep(i, N) {
        rep(j, A[i]) {
            ll g = gcd(S, j + 1);
            ll b = S / g;
            ll u = (j + 1) / g;
            res /= u;
            if (res > (1e18 + b - 1) / b + 10)return 1e18;
            res *= b;
            if (res > 1e18)return 1e18 + 1;
            S--;
        }
    }
    return res;
}

ll cnt() {
    vll A;
    ll k = 0;
    ll res = 1;
    ll N = US.size();
    rep(i, N) {
        if (!US[i])k++;
        else if (k != 0) {
            A.push_back(k);
            ll f = (F[k] + 1) / 2;
            if (res > (1e18 + f - 1) / f + 10)return 1e18 + 1;
            res *= f;
            k = 0;
        }
    }
    if (k != 0) {
        A.push_back(k);
        ll f = (F[k] + 1) / 2;
        if (res > (1e18 + f - 1) / f + 10)return 1e18 + 1;
        res *= f;
        k = 0;
    }
    ll pl = multinom(A);
    if (pl > 1e18)return 1e18 + 1;
    if (res > (1e18 + pl - 1) / pl + 10)return 1e18 + 1;
    res *= pl;
    return res;
}


void solve(ll N, ll K) {
    US.assign(N, false);
    vll AN;
    rep(i, N) {
        ll res = 0;
        vector<bool> nextOK(N, 1);
        ll pr = -1;
        rep(j, N) {
            if (US[j]) {
                nextOK[j] = 0;
                pr = j;
            }
            else {
                if (pr == -1)continue;
                if ((j - pr) % 2 == 0)continue;
                if ((j == 0 || US[j - 1]) && (j == N - 1 || US[j + 1]))continue;
                nextOK[j] = 0;
            }
        }
        bool E = 0;
        rep(j, N) {
            if (US[j])continue;
            if (!nextOK[j])continue;
            US[j] = 1;
            res = cnt();
            if (res >= K) {
                AN.push_back(j);
                E = 1;
                break;
            }
            else {
                K -= res;
            }
            US[j] = 0;
        }
        if (!E) {
            cout << -1 << endl;
            return;
        }
    }
    rep(i, N)cout << AN[i] + 1 << " \n"[i == N - 1];
}

int main() {

    ll N, K;
    cin >> N >> K;
    solve(N, K);
    
    //for (ll k = 1; k <= K; k++)cout << k << endl, solve(N, k);

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2

output:

2 1 3

result:

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

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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: 3584kb

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

3 1

output:

1 3 2

result:

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

Test #6:

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

input:

3 10

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

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

input:

3 52

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

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

input:

3 756

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

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

input:

3 7721

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

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

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: 3832kb

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: 3792kb

input:

5 85

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

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

input:

5 846

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

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

input:

5 6957

output:

-1

result:

ok 1 number(s): "-1"

Test #15:

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

input:

8 1

output:

1 3 2 5 4 7 6 8

result:

ok 8 numbers

Test #16:

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

input:

8 7

output:

1 3 2 5 7 8 4 6

result:

ok 8 numbers

Test #17:

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

input:

8 71

output:

1 3 7 5 4 2 6 8

result:

ok 8 numbers

Test #18:

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

input:

8 863

output:

3 2 7 5 1 6 8 4

result:

wrong answer 2nd numbers differ - expected: '5', found: '2'