Submission #1535461
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000*1000*1000+7;
vector<ll> fact;
int N, K;
vector<int> P;
struct BIT {
vector<int> tree;
void init() {
tree = vector<int>(4*N, 0);
}
void upd(int idx, int val, int l, int r, int n) {
if(idx < l || r < idx) return;
if(l == r) {
tree[n] = val;
return;
}
int m = (l + r)>>1;
upd(idx, val, l, m, 2*n);
upd(idx, val, m + 1, r, 2*n + 1);
tree[n] = tree[2*n] + tree[2*n + 1];
}
int quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return 0;
if(a <= l && r <= b) return tree[n];
int m = (l + r)>>1;
int L = quer(a, b, l, m, 2*n);
int R = quer(a, b, m + 1, r, 2*n + 1);
return L + R;
}
} bit, sub;
int main() {
fact.resize(500010);
fact[0] = 1;
for(int i = 1; i < 500010; i++) {
fact[i] = fact[i - 1] * i % mod;
}
scanf("%d", &N);
K = 0;
P.resize(N);
sub.init();
for(int i = 0; i < N; i++) {
scanf("%d", &P[i]);
P[i]--;
if(P[i] == -1) K++;
sub.upd(i, 1, 0, N - 1, 1);
}
ll sum = 1LL * N * (N - 1) / 2;
for(int i = 0; i < N; i++) {
if(P[i] != -1) sum -= P[i], sub.upd(P[i], 0, 0, N - 1, 1);
}
sum = (sum % mod + mod) % mod;
bit.init();
ll ans = 0;
ll tmp = 0;
int cnt = 0;
for(int i = 0; i < N; i++) {
if(P[i] == -1) {
ll a = sum * fact[K - 1] % mod;
ll b = tmp * fact[K - 1] % mod;
ll c = K < 2? 0 : (1LL * K * (K - 1) / 2 % mod) * fact[K - 2] % mod * cnt % mod;
ans += (a - b - c) * fact[N - i - 1] % mod, ans = (ans % mod + mod) % mod;
cnt++;
}
else {
bit.upd(P[i], 1, 0, N - 1, 1);
tmp += sub.quer(P[i] + 1, N - 1, 0, N - 1, 1);
tmp %= mod;
ll a = fact[K] * P[i] % mod;
ll b = fact[K] * bit.quer(0, P[i] - 1, 0, N - 1, 1) % mod;
ll c = K == 0? 0 : fact[K - 1] * sub.quer(0, P[i] - 1, 0, N - 1, 1) % mod * cnt % mod;
ans += (a - b - c) * fact[N - 1 - i] % mod, ans = (ans % mod + mod) % mod;
}
}
cout << (ans + fact[K]) % mod;
}
Submission Info
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:45:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:50:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &P[i]);
^
Judge Result
Set Name |
Sample |
Subtask |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
700 / 700 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt |
Subtask |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt, 2_051.txt, 2_052.txt, 2_053.txt, 2_054.txt, 2_055.txt, 2_056.txt, 2_057.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
6 ms |
4096 KB |
0_001.txt |
AC |
6 ms |
4096 KB |
0_002.txt |
AC |
6 ms |
4096 KB |
0_003.txt |
AC |
6 ms |
4096 KB |
0_004.txt |
AC |
6 ms |
4096 KB |
1_005.txt |
AC |
6 ms |
4096 KB |
1_006.txt |
AC |
6 ms |
4096 KB |
1_007.txt |
AC |
6 ms |
4096 KB |
1_008.txt |
AC |
6 ms |
4224 KB |
1_009.txt |
AC |
6 ms |
4224 KB |
1_010.txt |
AC |
6 ms |
4224 KB |
1_011.txt |
AC |
6 ms |
4224 KB |
1_012.txt |
AC |
7 ms |
4224 KB |
1_013.txt |
AC |
6 ms |
4224 KB |
1_014.txt |
AC |
7 ms |
4224 KB |
1_015.txt |
AC |
6 ms |
4224 KB |
1_016.txt |
AC |
7 ms |
4224 KB |
1_017.txt |
AC |
6 ms |
4096 KB |
1_018.txt |
AC |
7 ms |
4224 KB |
1_019.txt |
AC |
6 ms |
4224 KB |
1_020.txt |
AC |
8 ms |
4224 KB |
1_021.txt |
AC |
7 ms |
4224 KB |
1_022.txt |
AC |
7 ms |
4224 KB |
1_023.txt |
AC |
7 ms |
4224 KB |
1_024.txt |
AC |
8 ms |
4224 KB |
1_025.txt |
AC |
6 ms |
4096 KB |
1_026.txt |
AC |
7 ms |
4224 KB |
1_027.txt |
AC |
6 ms |
4224 KB |
1_028.txt |
AC |
6 ms |
4224 KB |
1_029.txt |
AC |
8 ms |
4224 KB |
1_030.txt |
AC |
7 ms |
4224 KB |
1_031.txt |
AC |
7 ms |
4224 KB |
1_032.txt |
AC |
7 ms |
4224 KB |
2_033.txt |
AC |
102 ms |
21760 KB |
2_034.txt |
AC |
53 ms |
12928 KB |
2_035.txt |
AC |
157 ms |
21760 KB |
2_036.txt |
AC |
141 ms |
20352 KB |
2_037.txt |
AC |
213 ms |
21760 KB |
2_038.txt |
AC |
177 ms |
19584 KB |
2_039.txt |
AC |
255 ms |
21760 KB |
2_040.txt |
AC |
123 ms |
12928 KB |
2_041.txt |
AC |
303 ms |
21760 KB |
2_042.txt |
AC |
62 ms |
7552 KB |
2_043.txt |
AC |
354 ms |
21760 KB |
2_044.txt |
AC |
226 ms |
15744 KB |
2_045.txt |
AC |
399 ms |
21760 KB |
2_046.txt |
AC |
375 ms |
20992 KB |
2_047.txt |
AC |
434 ms |
21760 KB |
2_048.txt |
AC |
183 ms |
11904 KB |
2_049.txt |
AC |
477 ms |
21760 KB |
2_050.txt |
AC |
313 ms |
15744 KB |
2_051.txt |
AC |
430 ms |
21760 KB |
2_052.txt |
AC |
389 ms |
20096 KB |
2_053.txt |
AC |
102 ms |
21760 KB |
2_054.txt |
AC |
519 ms |
21760 KB |
2_055.txt |
AC |
304 ms |
21760 KB |
2_056.txt |
AC |
302 ms |
21760 KB |
2_057.txt |
AC |
240 ms |
21760 KB |