oj.uz

Submission #737437

# Submission time Handle Problem Language Result Execution time Memory
737437 2023-05-07T07:42:38 Z Ronin13 Cryptography (NOI20_crypto) C++14
100 / 100
 392 ms 61232 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 10000001;
vector <int> bit(nmax);

const ll mod = 1e9 + 7;

int lsb(int x){
    return x & -x;
}

void add(int pos, int v, int n){
    while(pos <= n){
        bit[pos] += v;
        pos += lsb(pos);
    }
}

int get(int pos){
    int res = 0;
    while(pos){
        res += bit[pos];
        pos -= lsb(pos);
    }
    return res;
}

int main(){
    int n; cin >> n;
    int p[n + 1];
    for(int i = 1; i <= n ;++i)
        cin >> p[i];
    map <int,int> mp;
    int b[n + 1];
    for(int i = 1;i <= n ;i++){
        b[i] = p[i];
    }
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; i++){
        mp[b[i]] = i;
    }
    for(int i = 1; i <= n; ++i){
        add(i, 1, n);
        p[i] = mp[p[i]];
    }
    ll fact[n + 1];
    fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = fact[i - 1] * (ll)i % mod;
    }
    ll curans = 1;
    for(int i = 1; i <= n; i++){
        int x = p[i];
        ll o = get(x - 1);
        curans += fact[n - i] * o;
        curans %= mod;
        add(x, -1, n);
    }
    cout << curans << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39364 KB Output is correct
2 Correct 15 ms 39436 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39364 KB Output is correct
2 Correct 15 ms 39436 KB Output is correct
3 Correct 16 ms 39428 KB Output is correct
4 Correct 15 ms 39388 KB Output is correct
5 Correct 15 ms 39380 KB Output is correct
6 Correct 19 ms 39508 KB Output is correct
7 Correct 16 ms 39380 KB Output is correct
8 Correct 16 ms 39316 KB Output is correct
9 Correct 17 ms 39344 KB Output is correct
10 Correct 17 ms 39388 KB Output is correct
11 Correct 17 ms 39352 KB Output is correct
12 Correct 17 ms 39356 KB Output is correct
13 Correct 16 ms 39380 KB Output is correct
14 Correct 17 ms 39416 KB Output is correct
15 Correct 15 ms 39380 KB Output is correct
16 Correct 16 ms 39368 KB Output is correct
17 Correct 16 ms 39452 KB Output is correct
18 Correct 17 ms 39340 KB Output is correct
19 Correct 17 ms 39380 KB Output is correct
20 Correct 16 ms 39380 KB Output is correct
21 Correct 17 ms 39400 KB Output is correct
22 Correct 19 ms 39380 KB Output is correct
23 Correct 16 ms 39380 KB Output is correct
24 Correct 16 ms 39436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 237 ms 61068 KB Output is correct
3 Correct 233 ms 60988 KB Output is correct
4 Correct 224 ms 61228 KB Output is correct
5 Correct 221 ms 61004 KB Output is correct
6 Correct 221 ms 61060 KB Output is correct
7 Correct 225 ms 61004 KB Output is correct
8 Correct 226 ms 61084 KB Output is correct
9 Correct 224 ms 61004 KB Output is correct
10 Correct 222 ms 61076 KB Output is correct
11 Correct 224 ms 61076 KB Output is correct
12 Correct 229 ms 61036 KB Output is correct
13 Correct 223 ms 61032 KB Output is correct
14 Correct 231 ms 61072 KB Output is correct
15 Correct 225 ms 61064 KB Output is correct
16 Correct 225 ms 61088 KB Output is correct
17 Correct 221 ms 61132 KB Output is correct
18 Correct 220 ms 61056 KB Output is correct
19 Correct 219 ms 61108 KB Output is correct
20 Correct 220 ms 61076 KB Output is correct
21 Correct 227 ms 61088 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39448 KB Output is correct
2 Correct 194 ms 60200 KB Output is correct
3 Correct 203 ms 60152 KB Output is correct
4 Correct 192 ms 60052 KB Output is correct
5 Correct 201 ms 60156 KB Output is correct
6 Correct 193 ms 60064 KB Output is correct
7 Correct 193 ms 60112 KB Output is correct
8 Correct 191 ms 60148 KB Output is correct
9 Correct 197 ms 60040 KB Output is correct
10 Correct 196 ms 60064 KB Output is correct
11 Correct 194 ms 60108 KB Output is correct
12 Correct 192 ms 60112 KB Output is correct
13 Correct 207 ms 60116 KB Output is correct
14 Correct 190 ms 60052 KB Output is correct
15 Correct 196 ms 60140 KB Output is correct
16 Correct 193 ms 60108 KB Output is correct
17 Correct 209 ms 60108 KB Output is correct
18 Correct 203 ms 60112 KB Output is correct
19 Correct 204 ms 60136 KB Output is correct
20 Correct 196 ms 60044 KB Output is correct
21 Correct 200 ms 60104 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39448 KB Output is correct
2 Correct 16 ms 39528 KB Output is correct
3 Correct 18 ms 39640 KB Output is correct
4 Correct 20 ms 39584 KB Output is correct
5 Correct 17 ms 39568 KB Output is correct
6 Correct 18 ms 39636 KB Output is correct
7 Correct 17 ms 39568 KB Output is correct
8 Correct 17 ms 39592 KB Output is correct
9 Correct 18 ms 39584 KB Output is correct
10 Correct 19 ms 39636 KB Output is correct
11 Correct 20 ms 39636 KB Output is correct
12 Correct 19 ms 39636 KB Output is correct
13 Correct 17 ms 39636 KB Output is correct
14 Correct 17 ms 39636 KB Output is correct
15 Correct 15 ms 39380 KB Output is correct
16 Correct 17 ms 39580 KB Output is correct
17 Correct 18 ms 39636 KB Output is correct
18 Correct 18 ms 39608 KB Output is correct
19 Correct 17 ms 39640 KB Output is correct
20 Correct 18 ms 39608 KB Output is correct
21 Correct 17 ms 39576 KB Output is correct
22 Correct 17 ms 39560 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39364 KB Output is correct
2 Correct 15 ms 39436 KB Output is correct
3 Correct 16 ms 39428 KB Output is correct
4 Correct 15 ms 39388 KB Output is correct
5 Correct 15 ms 39380 KB Output is correct
6 Correct 19 ms 39508 KB Output is correct
7 Correct 16 ms 39380 KB Output is correct
8 Correct 16 ms 39316 KB Output is correct
9 Correct 17 ms 39344 KB Output is correct
10 Correct 17 ms 39388 KB Output is correct
11 Correct 17 ms 39352 KB Output is correct
12 Correct 17 ms 39356 KB Output is correct
13 Correct 16 ms 39380 KB Output is correct
14 Correct 17 ms 39416 KB Output is correct
15 Correct 15 ms 39380 KB Output is correct
16 Correct 16 ms 39368 KB Output is correct
17 Correct 16 ms 39452 KB Output is correct
18 Correct 17 ms 39340 KB Output is correct
19 Correct 17 ms 39380 KB Output is correct
20 Correct 16 ms 39380 KB Output is correct
21 Correct 17 ms 39400 KB Output is correct
22 Correct 19 ms 39380 KB Output is correct
23 Correct 16 ms 39380 KB Output is correct
24 Correct 16 ms 39436 KB Output is correct
25 Correct 17 ms 39448 KB Output is correct
26 Correct 16 ms 39528 KB Output is correct
27 Correct 18 ms 39640 KB Output is correct
28 Correct 20 ms 39584 KB Output is correct
29 Correct 17 ms 39568 KB Output is correct
30 Correct 18 ms 39636 KB Output is correct
31 Correct 17 ms 39568 KB Output is correct
32 Correct 17 ms 39592 KB Output is correct
33 Correct 18 ms 39584 KB Output is correct
34 Correct 19 ms 39636 KB Output is correct
35 Correct 20 ms 39636 KB Output is correct
36 Correct 19 ms 39636 KB Output is correct
37 Correct 17 ms 39636 KB Output is correct
38 Correct 17 ms 39636 KB Output is correct
39 Correct 15 ms 39380 KB Output is correct
40 Correct 17 ms 39580 KB Output is correct
41 Correct 18 ms 39636 KB Output is correct
42 Correct 18 ms 39608 KB Output is correct
43 Correct 17 ms 39640 KB Output is correct
44 Correct 18 ms 39608 KB Output is correct
45 Correct 17 ms 39576 KB Output is correct
46 Correct 17 ms 39560 KB Output is correct
47 Correct 16 ms 39424 KB Output is correct
48 Correct 17 ms 39592 KB Output is correct
49 Correct 17 ms 39636 KB Output is correct
50 Correct 18 ms 39596 KB Output is correct
51 Correct 17 ms 39660 KB Output is correct
52 Correct 17 ms 39648 KB Output is correct
53 Correct 18 ms 39656 KB Output is correct
54 Correct 18 ms 39636 KB Output is correct
55 Correct 17 ms 39636 KB Output is correct
56 Correct 18 ms 39632 KB Output is correct
57 Correct 19 ms 39608 KB Output is correct
58 Correct 18 ms 39540 KB Output is correct
59 Correct 19 ms 39624 KB Output is correct
60 Correct 17 ms 39636 KB Output is correct
61 Correct 17 ms 39380 KB Output is correct
62 Correct 17 ms 39548 KB Output is correct
63 Correct 18 ms 39568 KB Output is correct
64 Correct 17 ms 39636 KB Output is correct
65 Correct 17 ms 39636 KB Output is correct
66 Correct 17 ms 39592 KB Output is correct
67 Correct 18 ms 39576 KB Output is correct
68 Correct 17 ms 39616 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39448 KB Output is correct
2 Correct 194 ms 60200 KB Output is correct
3 Correct 203 ms 60152 KB Output is correct
4 Correct 192 ms 60052 KB Output is correct
5 Correct 201 ms 60156 KB Output is correct
6 Correct 193 ms 60064 KB Output is correct
7 Correct 193 ms 60112 KB Output is correct
8 Correct 191 ms 60148 KB Output is correct
9 Correct 197 ms 60040 KB Output is correct
10 Correct 196 ms 60064 KB Output is correct
11 Correct 194 ms 60108 KB Output is correct
12 Correct 192 ms 60112 KB Output is correct
13 Correct 207 ms 60116 KB Output is correct
14 Correct 190 ms 60052 KB Output is correct
15 Correct 196 ms 60140 KB Output is correct
16 Correct 193 ms 60108 KB Output is correct
17 Correct 209 ms 60108 KB Output is correct
18 Correct 203 ms 60112 KB Output is correct
19 Correct 204 ms 60136 KB Output is correct
20 Correct 196 ms 60044 KB Output is correct
21 Correct 200 ms 60104 KB Output is correct
22 Correct 17 ms 39448 KB Output is correct
23 Correct 16 ms 39528 KB Output is correct
24 Correct 18 ms 39640 KB Output is correct
25 Correct 20 ms 39584 KB Output is correct
26 Correct 17 ms 39568 KB Output is correct
27 Correct 18 ms 39636 KB Output is correct
28 Correct 17 ms 39568 KB Output is correct
29 Correct 17 ms 39592 KB Output is correct
30 Correct 18 ms 39584 KB Output is correct
31 Correct 19 ms 39636 KB Output is correct
32 Correct 20 ms 39636 KB Output is correct
33 Correct 19 ms 39636 KB Output is correct
34 Correct 17 ms 39636 KB Output is correct
35 Correct 17 ms 39636 KB Output is correct
36 Correct 15 ms 39380 KB Output is correct
37 Correct 17 ms 39580 KB Output is correct
38 Correct 18 ms 39636 KB Output is correct
39 Correct 18 ms 39608 KB Output is correct
40 Correct 17 ms 39640 KB Output is correct
41 Correct 18 ms 39608 KB Output is correct
42 Correct 17 ms 39576 KB Output is correct
43 Correct 17 ms 39560 KB Output is correct
44 Correct 17 ms 39380 KB Output is correct
45 Correct 341 ms 60172 KB Output is correct
46 Correct 329 ms 60188 KB Output is correct
47 Correct 333 ms 60300 KB Output is correct
48 Correct 350 ms 60108 KB Output is correct
49 Correct 335 ms 60112 KB Output is correct
50 Correct 329 ms 60112 KB Output is correct
51 Correct 347 ms 60152 KB Output is correct
52 Correct 363 ms 60048 KB Output is correct
53 Correct 362 ms 60156 KB Output is correct
54 Correct 357 ms 60040 KB Output is correct
55 Correct 354 ms 60172 KB Output is correct
56 Correct 345 ms 60112 KB Output is correct
57 Correct 350 ms 60048 KB Output is correct
58 Correct 18 ms 39380 KB Output is correct
59 Correct 391 ms 60112 KB Output is correct
60 Correct 376 ms 60112 KB Output is correct
61 Correct 363 ms 60060 KB Output is correct
62 Correct 360 ms 60144 KB Output is correct
63 Correct 375 ms 60036 KB Output is correct
64 Correct 346 ms 60152 KB Output is correct
65 Correct 372 ms 60156 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39364 KB Output is correct
2 Correct 15 ms 39436 KB Output is correct
3 Correct 16 ms 39428 KB Output is correct
4 Correct 15 ms 39388 KB Output is correct
5 Correct 15 ms 39380 KB Output is correct
6 Correct 19 ms 39508 KB Output is correct
7 Correct 16 ms 39380 KB Output is correct
8 Correct 16 ms 39316 KB Output is correct
9 Correct 17 ms 39344 KB Output is correct
10 Correct 17 ms 39388 KB Output is correct
11 Correct 17 ms 39352 KB Output is correct
12 Correct 17 ms 39356 KB Output is correct
13 Correct 16 ms 39380 KB Output is correct
14 Correct 17 ms 39416 KB Output is correct
15 Correct 15 ms 39380 KB Output is correct
16 Correct 16 ms 39368 KB Output is correct
17 Correct 16 ms 39452 KB Output is correct
18 Correct 17 ms 39340 KB Output is correct
19 Correct 17 ms 39380 KB Output is correct
20 Correct 16 ms 39380 KB Output is correct
21 Correct 17 ms 39400 KB Output is correct
22 Correct 19 ms 39380 KB Output is correct
23 Correct 16 ms 39380 KB Output is correct
24 Correct 16 ms 39436 KB Output is correct
25 Correct 18 ms 39380 KB Output is correct
26 Correct 237 ms 61068 KB Output is correct
27 Correct 233 ms 60988 KB Output is correct
28 Correct 224 ms 61228 KB Output is correct
29 Correct 221 ms 61004 KB Output is correct
30 Correct 221 ms 61060 KB Output is correct
31 Correct 225 ms 61004 KB Output is correct
32 Correct 226 ms 61084 KB Output is correct
33 Correct 224 ms 61004 KB Output is correct
34 Correct 222 ms 61076 KB Output is correct
35 Correct 224 ms 61076 KB Output is correct
36 Correct 229 ms 61036 KB Output is correct
37 Correct 223 ms 61032 KB Output is correct
38 Correct 231 ms 61072 KB Output is correct
39 Correct 225 ms 61064 KB Output is correct
40 Correct 225 ms 61088 KB Output is correct
41 Correct 221 ms 61132 KB Output is correct
42 Correct 220 ms 61056 KB Output is correct
43 Correct 219 ms 61108 KB Output is correct
44 Correct 220 ms 61076 KB Output is correct
45 Correct 227 ms 61088 KB Output is correct
46 Correct 16 ms 39448 KB Output is correct
47 Correct 194 ms 60200 KB Output is correct
48 Correct 203 ms 60152 KB Output is correct
49 Correct 192 ms 60052 KB Output is correct
50 Correct 201 ms 60156 KB Output is correct
51 Correct 193 ms 60064 KB Output is correct
52 Correct 193 ms 60112 KB Output is correct
53 Correct 191 ms 60148 KB Output is correct
54 Correct 197 ms 60040 KB Output is correct
55 Correct 196 ms 60064 KB Output is correct
56 Correct 194 ms 60108 KB Output is correct
57 Correct 192 ms 60112 KB Output is correct
58 Correct 207 ms 60116 KB Output is correct
59 Correct 190 ms 60052 KB Output is correct
60 Correct 196 ms 60140 KB Output is correct
61 Correct 193 ms 60108 KB Output is correct
62 Correct 209 ms 60108 KB Output is correct
63 Correct 203 ms 60112 KB Output is correct
64 Correct 204 ms 60136 KB Output is correct
65 Correct 196 ms 60044 KB Output is correct
66 Correct 200 ms 60104 KB Output is correct
67 Correct 17 ms 39448 KB Output is correct
68 Correct 16 ms 39528 KB Output is correct
69 Correct 18 ms 39640 KB Output is correct
70 Correct 20 ms 39584 KB Output is correct
71 Correct 17 ms 39568 KB Output is correct
72 Correct 18 ms 39636 KB Output is correct
73 Correct 17 ms 39568 KB Output is correct
74 Correct 17 ms 39592 KB Output is correct
75 Correct 18 ms 39584 KB Output is correct
76 Correct 19 ms 39636 KB Output is correct
77 Correct 20 ms 39636 KB Output is correct
78 Correct 19 ms 39636 KB Output is correct
79 Correct 17 ms 39636 KB Output is correct
80 Correct 17 ms 39636 KB Output is correct
81 Correct 15 ms 39380 KB Output is correct
82 Correct 17 ms 39580 KB Output is correct
83 Correct 18 ms 39636 KB Output is correct
84 Correct 18 ms 39608 KB Output is correct
85 Correct 17 ms 39640 KB Output is correct
86 Correct 18 ms 39608 KB Output is correct
87 Correct 17 ms 39576 KB Output is correct
88 Correct 17 ms 39560 KB Output is correct
89 Correct 16 ms 39424 KB Output is correct
90 Correct 17 ms 39592 KB Output is correct
91 Correct 17 ms 39636 KB Output is correct
92 Correct 18 ms 39596 KB Output is correct
93 Correct 17 ms 39660 KB Output is correct
94 Correct 17 ms 39648 KB Output is correct
95 Correct 18 ms 39656 KB Output is correct
96 Correct 18 ms 39636 KB Output is correct
97 Correct 17 ms 39636 KB Output is correct
98 Correct 18 ms 39632 KB Output is correct
99 Correct 19 ms 39608 KB Output is correct
100 Correct 18 ms 39540 KB Output is correct
101 Correct 19 ms 39624 KB Output is correct
102 Correct 17 ms 39636 KB Output is correct
103 Correct 17 ms 39380 KB Output is correct
104 Correct 17 ms 39548 KB Output is correct
105 Correct 18 ms 39568 KB Output is correct
106 Correct 17 ms 39636 KB Output is correct
107 Correct 17 ms 39636 KB Output is correct
108 Correct 17 ms 39592 KB Output is correct
109 Correct 18 ms 39576 KB Output is correct
110 Correct 17 ms 39616 KB Output is correct
111 Correct 17 ms 39380 KB Output is correct
112 Correct 341 ms 60172 KB Output is correct
113 Correct 329 ms 60188 KB Output is correct
114 Correct 333 ms 60300 KB Output is correct
115 Correct 350 ms 60108 KB Output is correct
116 Correct 335 ms 60112 KB Output is correct
117 Correct 329 ms 60112 KB Output is correct
118 Correct 347 ms 60152 KB Output is correct
119 Correct 363 ms 60048 KB Output is correct
120 Correct 362 ms 60156 KB Output is correct
121 Correct 357 ms 60040 KB Output is correct
122 Correct 354 ms 60172 KB Output is correct
123 Correct 345 ms 60112 KB Output is correct
124 Correct 350 ms 60048 KB Output is correct
125 Correct 18 ms 39380 KB Output is correct
126 Correct 391 ms 60112 KB Output is correct
127 Correct 376 ms 60112 KB Output is correct
128 Correct 363 ms 60060 KB Output is correct
129 Correct 360 ms 60144 KB Output is correct
130 Correct 375 ms 60036 KB Output is correct
131 Correct 346 ms 60152 KB Output is correct
132 Correct 372 ms 60156 KB Output is correct
133 Correct 17 ms 39380 KB Output is correct
134 Correct 385 ms 61084 KB Output is correct
135 Correct 376 ms 61004 KB Output is correct
136 Correct 383 ms 61184 KB Output is correct
137 Correct 360 ms 61068 KB Output is correct
138 Correct 378 ms 61204 KB Output is correct
139 Correct 359 ms 61072 KB Output is correct
140 Correct 378 ms 61112 KB Output is correct
141 Correct 368 ms 61108 KB Output is correct
142 Correct 364 ms 61196 KB Output is correct
143 Correct 376 ms 61004 KB Output is correct
144 Correct 384 ms 61064 KB Output is correct
145 Correct 378 ms 61040 KB Output is correct
146 Correct 392 ms 61068 KB Output is correct
147 Correct 16 ms 39380 KB Output is correct
148 Correct 372 ms 61064 KB Output is correct
149 Correct 378 ms 61160 KB Output is correct
150 Correct 369 ms 61076 KB Output is correct
151 Correct 383 ms 61188 KB Output is correct
152 Correct 384 ms 61068 KB Output is correct
153 Correct 365 ms 61232 KB Output is correct
154 Correct 380 ms 61060 KB Output is correct