QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#377588#8107. PermutationSolitaryDream#AC ✓59ms37284kbC++172.1kb2024-04-05 15:39:372024-04-05 15:39:39

Judging History

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

  • [2024-04-05 15:39:39]
  • 评测
  • 测评结果:AC
  • 用时:59ms
  • 内存:37284kb
  • [2024-04-05 15:39:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=250000+50;
const ll INF=2e18;
vector<ll> f[N];
ll qry(int x,ll y) {
    y=min(y,(ll)x*(x-1)/2-y);
    if(y<0) return 0;
    if(y<f[x].size()) return f[x][y];
    else return INF;
}
// ll QRY(int x,ll l,ll r) {
//     ll s=0;
//     FOR(i,l,r) s+=qry(x,i);
//     return s;
// }
int ans[N];

struct BIT{
    int c[1<<20];

    void add(int x,int v)
    {
        while(x<(1<<20))
        {
            c[x]+=v;
            x+=x&-x;
        }
    }

    int qry(int k)
    {
        int ret=0;
        for(int i=19;i>=0;i--)
            if(c[ret+(1<<i)]<k)
                k-=c[ret+(1<<i)],ret+=(1<<i);
        return ret+1;
    }
} T;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    f[1]={1};
    int tot=0;
    FOR(i,2,n) {
        for(ll k=0; k<=(ll)i*(i-1)/2; ++k) {
            f[i].push_back(0);
            for(int j=1; j-1<=k && j<=i; ++j) {
                f[i][k]+=qry(i-1,k-(j-1));
                if(f[i][k]>=INF) f[i][k]=INF;
            }
            if(f[i][k]>=INF) {
                break;
            }
        }
        tot+=f[i].size();
    }
    // cerr << tot << '\n';
    // cerr << tot << '\n';
    ll K;
    cin >> K;
    ll s=(ll)n*(n-1)/2;
    if(s&1) {
        cout << "NO\n";
        return 0;
    }
    s/=2;
    if(qry(n,s)<K) {
        cout << "NO\n";
        return 0;
    }
    FOR(i,1,n) T.add(i,1);
    DOR(i,n,1) {
        FOR(j,max(1ll,-(i-1)*(i-2)/2+s+1),i) {
            ll c=qry(i-1,s-(j-1));
            if(c<K) {
                K-=c;
                continue;
            }
            s-=j-1;
            int r=T.qry(j);
            ans[n-i+1]=r;
            T.add(r,-1);
            // cerr << i << ' ' << j << endl;
            break;
        }
    }
    cout << "YES\n";
    FOR(i,1,n) cout << ans[i] << " \n"[i==n];
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 3

output:

YES
2 4 1 3

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 10832kb

input:

4 57

output:

NO

result:

ok single line: 'NO'

Test #3:

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

input:

1 1

output:

YES
1

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 2ms
memory: 10032kb

input:

1 2

output:

NO

result:

ok single line: 'NO'

Test #5:

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

input:

1 42

output:

NO

result:

ok single line: 'NO'

Test #6:

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

input:

4 1

output:

YES
1 4 3 2

result:

ok 2 lines

Test #7:

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

input:

4 6

output:

YES
4 1 2 3

result:

ok 2 lines

Test #8:

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

input:

4 7

output:

NO

result:

ok single line: 'NO'

Test #9:

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

input:

5 13

output:

YES
3 4 2 1 5

result:

ok 2 lines

Test #10:

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

input:

5 21

output:

YES
5 1 3 2 4

result:

ok 2 lines

Test #11:

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

input:

5 22

output:

YES
5 2 1 3 4

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 2ms
memory: 11264kb

input:

5 23

output:

NO

result:

ok single line: 'NO'

Test #13:

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

input:

8 3836

output:

YES
8 7 2 1 3 4 5 6

result:

ok 2 lines

Test #14:

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

input:

8 3837

output:

NO

result:

ok single line: 'NO'

Test #15:

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

input:

9 29228

output:

YES
9 8 4 1 2 3 5 6 7

result:

ok 2 lines

Test #16:

score: 0
Accepted
time: 2ms
memory: 10636kb

input:

9 29229

output:

NO

result:

ok single line: 'NO'

Test #17:

score: 0
Accepted
time: 2ms
memory: 11208kb

input:

9 32768

output:

NO

result:

ok single line: 'NO'

Test #18:

score: 0
Accepted
time: 2ms
memory: 9656kb

input:

2 1

output:

NO

result:

ok single line: 'NO'

Test #19:

score: 0
Accepted
time: 2ms
memory: 10972kb

input:

7 1

output:

NO

result:

ok single line: 'NO'

Test #20:

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

input:

13 296643390

output:

YES
13 12 11 7 1 2 3 4 5 6 8 9 10

result:

ok 2 lines

Test #21:

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

input:

13 296643391

output:

NO

result:

ok single line: 'NO'

Test #22:

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

input:

20 62119523114983223

output:

YES
20 19 18 17 16 10 2 1 3 4 5 6 7 8 9 11 12 13 14 15

result:

ok 2 lines

Test #23:

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

input:

20 62119523114983224

output:

YES
20 19 18 17 16 11 1 2 3 4 5 6 7 8 9 10 12 13 14 15

result:

ok 2 lines

Test #24:

score: 0
Accepted
time: 2ms
memory: 10364kb

input:

20 62119523114983225

output:

NO

result:

ok single line: 'NO'

Test #25:

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

input:

21 1

output:

YES
1 2 3 4 5 6 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7

result:

ok 2 lines

Test #26:

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

input:

21 1000000000000000000

output:

YES
17 21 14 6 9 4 3 11 7 2 20 1 18 15 12 16 5 10 8 13 19

result:

ok 2 lines

Test #27:

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

input:

44 333333333333333333

output:

YES
1 2 3 4 5 6 7 8 9 10 11 21 42 44 41 40 43 38 39 35 34 37 36 32 31 33 29 27 28 25 30 26 23 24 15 22 18 16 20 19 17 12 13 14

result:

ok 2 lines

Test #28:

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

input:

49 600000000000000000

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 37 47 49 44 46 45 48 43 42 41 39 40 35 38 33 31 36 34 30 27 32 25 28 29 26 24 23 17 22 20 19 21 18 16 15 14

result:

ok 2 lines

Test #29:

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

input:

16 738680521142

output:

YES
16 15 14 13 7 1 2 3 4 5 6 8 9 10 11 12

result:

ok 2 lines

Test #30:

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

input:

16 738680521143

output:

NO

result:

ok single line: 'NO'

Test #31:

score: 0
Accepted
time: 2ms
memory: 11252kb

input:

350 702274833889168257

output:

NO

result:

ok single line: 'NO'

Test #32:

score: 0
Accepted
time: 2ms
memory: 10280kb

input:

347 823694565238057857

output:

NO

result:

ok single line: 'NO'

Test #33:

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

input:

348 548514836018174081

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #34:

score: 0
Accepted
time: 2ms
memory: 17240kb

input:

349 1000000000000000000

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #35:

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

input:

17 11501573822788

output:

YES
17 16 15 14 11 1 2 3 4 5 6 7 8 9 10 12 13

result:

ok 2 lines

Test #36:

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

input:

17 11501573822789

output:

NO

result:

ok single line: 'NO'

Test #37:

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

input:

1536 1000000000000000000

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #38:

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

input:

1533 1

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #39:

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

input:

1534 639944301316494081

output:

NO

result:

ok single line: 'NO'

Test #40:

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

input:

1535 133749702370803553

output:

NO

result:

ok single line: 'NO'

Test #41:

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

input:

12 25598186

output:

YES
12 11 10 4 1 2 3 5 6 7 8 9

result:

ok 2 lines

Test #42:

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

input:

12 25598187

output:

NO

result:

ok single line: 'NO'

Test #43:

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

input:

5000 1

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #44:

score: 0
Accepted
time: 5ms
memory: 16592kb

input:

4997 577621398254762881

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #45:

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

input:

4998 1000000000000000000

output:

NO

result:

ok single line: 'NO'

Test #46:

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

input:

4999 1000000000000000000

output:

NO

result:

ok single line: 'NO'

Test #47:

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

input:

8 3836

output:

YES
8 7 2 1 3 4 5 6

result:

ok 2 lines

Test #48:

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

input:

8 3837

output:

NO

result:

ok single line: 'NO'

Test #49:

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

input:

30000 15298495309447071

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #50:

score: 0
Accepted
time: 2ms
memory: 19616kb

input:

29997 253859976519879617

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #51:

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

input:

29998 1

output:

NO

result:

ok single line: 'NO'

Test #52:

score: 0
Accepted
time: 7ms
memory: 13888kb

input:

29999 1000000000000000000

output:

NO

result:

ok single line: 'NO'

Test #53:

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

input:

5 10

output:

YES
3 2 4 5 1

result:

ok 2 lines

Test #54:

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

input:

5 25

output:

NO

result:

ok single line: 'NO'

Test #55:

score: 0
Accepted
time: 17ms
memory: 22152kb

input:

75000 1000000000000000000

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #56:

score: 0
Accepted
time: 19ms
memory: 23520kb

input:

74997 1

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #57:

score: 0
Accepted
time: 7ms
memory: 16220kb

input:

74998 952975592247715841

output:

NO

result:

ok single line: 'NO'

Test #58:

score: 0
Accepted
time: 10ms
memory: 17076kb

input:

74999 563899854863562881

output:

NO

result:

ok single line: 'NO'

Test #59:

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

input:

20 62119523114983182

output:

YES
20 19 18 17 16 9 1 2 4 3 5 7 6 8 10 11 12 13 14 15

result:

ok 2 lines

Test #60:

score: 0
Accepted
time: 2ms
memory: 10408kb

input:

20 62119523114983324

output:

NO

result:

ok single line: 'NO'

Test #61:

score: 0
Accepted
time: 23ms
memory: 26996kb

input:

125000 890645059675041665

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #62:

score: 0
Accepted
time: 28ms
memory: 27396kb

input:

124997 1

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #63:

score: 0
Accepted
time: 16ms
memory: 19624kb

input:

124998 873954992112723841

output:

NO

result:

ok single line: 'NO'

Test #64:

score: 0
Accepted
time: 16ms
memory: 19640kb

input:

124999 248632969637282529

output:

NO

result:

ok single line: 'NO'

Test #65:

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

input:

17 11501573822775

output:

YES
17 16 15 14 9 2 3 1 4 5 6 7 8 10 11 12 13

result:

ok 2 lines

Test #66:

score: 0
Accepted
time: 2ms
memory: 9832kb

input:

17 11501573823343

output:

NO

result:

ok single line: 'NO'

Test #67:

score: 0
Accepted
time: 38ms
memory: 31452kb

input:

175000 1000000000000000000

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #68:

score: 0
Accepted
time: 32ms
memory: 30660kb

input:

174997 328322156846141249

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #69:

score: 0
Accepted
time: 20ms
memory: 24460kb

input:

174998 184010129245469601

output:

NO

result:

ok single line: 'NO'

Test #70:

score: 0
Accepted
time: 21ms
memory: 24652kb

input:

174999 988653544556724225

output:

NO

result:

ok single line: 'NO'

Test #71:

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

input:

16 738680521137

output:

YES
16 15 14 13 6 1 2 3 4 7 5 8 9 10 11 12

result:

ok 2 lines

Test #72:

score: 0
Accepted
time: 2ms
memory: 10300kb

input:

16 738680521147

output:

NO

result:

ok single line: 'NO'

Test #73:

score: 0
Accepted
time: 51ms
memory: 37184kb

input:

250000 265999253667994753

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #74:

score: 0
Accepted
time: 59ms
memory: 37284kb

input:

249997 1000000000000000000

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 2 lines

Test #75:

score: 0
Accepted
time: 35ms
memory: 30604kb

input:

249998 994057636750856961

output:

NO

result:

ok single line: 'NO'

Test #76:

score: 0
Accepted
time: 34ms
memory: 29796kb

input:

249999 728689378265228289

output:

NO

result:

ok single line: 'NO'