Submission #946245
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i) #define debug(...) fprintf(stderr, __VA_ARGS__) #define mp make_pair #define x first #define y second #define pb push_back #define SZ(x) (int((x).size())) #define ALL(x) (x).begin(), (x).end() template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } typedef long long LL; const int oo = 0x3f3f3f3f; const int Mod = 1e9 + 7; const int maxn = 500100; int n; int a[maxn + 5]; int fac[maxn + 5]; bool appear[maxn + 5]; int suf[maxn + 5], pre[maxn + 5]; int main() { #ifdef matthew99 freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif memset(appear, 0, sizeof appear); scanf("%d", &n); REP(i, 0, n) scanf("%d", a + i), --a[i], appear[a[i]] = 1; suf[n] = 0; for (int i = n - 1; i >= 0; --i) suf[i] = suf[i + 1] + (!appear[i]); pre[0] = 0; REP(i, 0, n) pre[i + 1] = pre[i] + (!appear[i]); fac[0] = 1; REP(i, 0, n) fac[i + 1] = (LL)fac[i] * (i + 1) % Mod; int cnt = 0; REP(i, 0, n) if (!~a[i]) ++cnt; int sum = 0; REP(i, 0, n) if (!appear[i]) (sum += i) %= Mod; int ret = fac[cnt]; int res = 0; REP(i, 0, n) if (!~a[i]) (res += fac[n - i - 1]) %= Mod; int tmp = ((LL)cnt * (cnt - 1) >> 1) % Mod; int now = 0; static int fen[maxn + 5]; memset(fen, 0, sizeof fen); REP(i, 0, n) { if (!~a[i]) { (ret += (LL)sum * fac[cnt - 1] % Mod * fac[n - i - 1] % Mod) %= Mod; if (cnt > 1) (ret -= (LL)now * tmp % Mod * fac[cnt - 2] % Mod * fac[n - i - 1] % Mod) %= Mod; ++now; (res -= fac[n - i - 1]) %= Mod; } else { if (cnt) (ret -= (LL)res * suf[a[i]] % Mod * fac[cnt - 1] % Mod) %= Mod; int num = a[i]; for (int k = a[i]; k > 0; k -= k & -k) num -= fen[k]; (ret += (LL)num * fac[cnt] % Mod * fac[n - i - 1] % Mod) %= Mod; if (cnt) (ret -= ((LL)now * pre[a[i]] % Mod * fac[cnt - 1] % Mod * fac[n - i - 1] % Mod)) %= Mod; for (int k = a[i] + 1; k <= n; k += k & -k) ++fen[k]; } } (ret += Mod) %= Mod; printf("%d\n", ret); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Encyclopedia of Permutations |
User | matthew99 |
Language | C++14 (GCC 5.4.1) |
Score | 1200 |
Code Size | 2247 Byte |
Status | AC |
Exec Time | 186 ms |
Memory | 10624 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:40:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ^ ./Main.cpp:41:59: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] REP(i, 0, n) scanf("%d", a + i), --a[i], appear[a[i]] = 1; ^
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 | 2688 KB |
0_001.txt | AC | 6 ms | 2816 KB |
0_002.txt | AC | 6 ms | 2688 KB |
0_003.txt | AC | 6 ms | 2688 KB |
0_004.txt | AC | 6 ms | 2688 KB |
1_005.txt | AC | 6 ms | 2688 KB |
1_006.txt | AC | 6 ms | 2688 KB |
1_007.txt | AC | 6 ms | 2688 KB |
1_008.txt | AC | 6 ms | 2688 KB |
1_009.txt | AC | 6 ms | 2688 KB |
1_010.txt | AC | 6 ms | 2688 KB |
1_011.txt | AC | 6 ms | 2816 KB |
1_012.txt | AC | 6 ms | 2688 KB |
1_013.txt | AC | 6 ms | 2688 KB |
1_014.txt | AC | 6 ms | 2688 KB |
1_015.txt | AC | 6 ms | 2688 KB |
1_016.txt | AC | 6 ms | 2688 KB |
1_017.txt | AC | 6 ms | 2688 KB |
1_018.txt | AC | 6 ms | 2688 KB |
1_019.txt | AC | 6 ms | 2688 KB |
1_020.txt | AC | 6 ms | 2688 KB |
1_021.txt | AC | 6 ms | 2688 KB |
1_022.txt | AC | 6 ms | 2688 KB |
1_023.txt | AC | 6 ms | 2688 KB |
1_024.txt | AC | 6 ms | 2688 KB |
1_025.txt | AC | 6 ms | 2688 KB |
1_026.txt | AC | 6 ms | 2688 KB |
1_027.txt | AC | 6 ms | 2688 KB |
1_028.txt | AC | 6 ms | 2816 KB |
1_029.txt | AC | 6 ms | 2688 KB |
1_030.txt | AC | 6 ms | 2816 KB |
1_031.txt | AC | 6 ms | 2688 KB |
1_032.txt | AC | 6 ms | 2688 KB |
2_033.txt | AC | 67 ms | 10496 KB |
2_034.txt | AC | 37 ms | 6656 KB |
2_035.txt | AC | 88 ms | 10496 KB |
2_036.txt | AC | 81 ms | 9856 KB |
2_037.txt | AC | 107 ms | 10624 KB |
2_038.txt | AC | 94 ms | 9600 KB |
2_039.txt | AC | 122 ms | 10496 KB |
2_040.txt | AC | 59 ms | 6656 KB |
2_041.txt | AC | 138 ms | 10624 KB |
2_042.txt | AC | 23 ms | 4224 KB |
2_043.txt | AC | 149 ms | 10496 KB |
2_044.txt | AC | 92 ms | 7808 KB |
2_045.txt | AC | 160 ms | 10496 KB |
2_046.txt | AC | 153 ms | 10240 KB |
2_047.txt | AC | 170 ms | 10496 KB |
2_048.txt | AC | 61 ms | 6272 KB |
2_049.txt | AC | 179 ms | 10496 KB |
2_050.txt | AC | 107 ms | 7808 KB |
2_051.txt | AC | 111 ms | 10624 KB |
2_052.txt | AC | 98 ms | 9728 KB |
2_053.txt | AC | 68 ms | 10496 KB |
2_054.txt | AC | 186 ms | 10624 KB |
2_055.txt | AC | 85 ms | 10496 KB |
2_056.txt | AC | 86 ms | 10496 KB |
2_057.txt | AC | 81 ms | 10496 KB |