QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#786813#4252. Permutationisirazeev10 1ms3884kbC++231.5kb2024-11-26 23:40:172024-11-26 23:40:18

Judging History

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

  • [2024-11-26 23:40:18]
  • 评测
  • 测评结果:10
  • 用时:1ms
  • 内存:3884kb
  • [2024-11-26 23:40:17]
  • 提交

answer

#include <bits/stdc++.h>

#include "perm.h"

using namespace std;

void mul2(vector<int> &p) {
    p.emplace_back((int) p.size());
}

void add1(vector<int> &p) {
    for (int &i: p) i++;
    p.emplace_back(0);
}

bool isGood(vector<int> p) {
    int pos1, pos0;
    for (int i = 0; i < (int) p.size(); i++) {
        if (p[i] == 1) pos1 = i;
        if (p[i] == 0) pos0 = i;
    }
    return pos1 < pos0;
}

std::vector<int> construct_permutation(long long k) {
    if (k <= 91) {
        vector<int> res(k - 1);
        iota(res.begin(), res.end(), 0);
        reverse(res.begin(), res.end());
        return res;
    }
    vector<int> operations;
    while (k > 1) {
        operations.emplace_back(k % 4);
        k /= 4;
    }
    vector<int> res;
    if (operations.back() == 0) res = {0, 1};
    else if (operations.back() == 1) res = {1, 2, 0};
    else if (operations.back() == 2) res = {1, 0, 2};
    else res = {2, 1, 3, 0};
    operations.pop_back();
    reverse(operations.begin(), operations.end());
    for (int r: operations) {
        if (r == 0) {
            mul2(res), mul2(res);
        } else if (r == 1) {
            mul2(res), mul2(res), add1(res);
        } else if (r == 2) {
            mul2(res), add1(res), mul2(res);
        } else {
            if (isGood(res)) {
                mul2(res), mul2(res);
                for (int &i: res)
                    if (i > 1) ++i;
                res.emplace_back(2);
            } else {
                mul2(res), add1(res), mul2(res), add1(res);
            }
        }
    }
    return res;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 3820kb

input:

a92b3f80-b312-8377-273c-3916024d7f2a
89
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

output:

6cad0f33-b1bd-3a3e-1a8d-c4af23adfcbf
OK
1
0
2
1 0
3
2 1 0
4
3 2 1 0
5
4 3 2 1 0
6
5 4 3 2 1 0
7
6 5 4 3 2 1 0
8
7 6 5 4 3 2 1 0
9
8 7 6 5 4 3 2 1 0
10
9 8 7 6 5 4 3 2 1 0
11
10 9 8 7 6 5 4 3 2 1 0
12
11 10 9 8 7 6 5 4 3 2 1 0
13
12 11 10 9 8 7 6 5 4 3 2 1 0
14
13 12 11 10 9 8 7 6 5 4 3 2 1 0
15
14 1...

result:

ok 

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 3884kb

input:

a92b3f80-b312-8377-273c-3916024d7f2a
100
39993
85709
48645
25391
15360
54084
28947
18808
86735
316
14357
82845
96210
16242
58466
43439
77462
70742
76176
20397
30314
22634
29622
81835
31904
81283
37072
36527
26764
55878
72762
5262
34915
63468
20595
66579
77373
36670
89340
83384
73268
31960
67318
3908...

output:

6cad0f33-b1bd-3a3e-1a8d-c4af23adfcbf
OK
22
6 3 7 8 9 2 10 11 5 12 13 14 15 16 17 4 18 1 19 20 21 0
22
5 7 2 8 9 10 11 6 12 1 13 14 15 4 16 17 18 19 3 20 21 0
22
4 3 7 8 9 6 10 11 5 12 2 13 14 15 16 17 18 19 1 20 21 0
19
4 1 6 7 8 9 10 5 11 12 13 0 14 15 16 3 17 18 2
17
3 1 4 0 5 6 2 7 8 9 10 11 12 1...

result:

wrong answer