Submission #945975
Source Code Expand
#ifdef DEBUG #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> using namespace std; mt19937 mrand(random_device{} ()); int rnd(int x) { return mrand() % x; } typedef long double ld; typedef long long ll; #ifdef DEBUG #define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr) #else #define eprintf(...) ; #endif #define pb push_back #define mp make_pair #define sz(x) ((int) (x).size()) #define TASK "text" const int inf = (int) 1.01e9; const ld eps = 1e-9; const ld pi = acos((ld) -1.0); const int mod = (int) 1e9 + 7; int mult(int x, int y) { return (long long) x * y % mod; } void add(int &x, int y) { if ((x += y) >= mod) { x -= mod; } } const int maxn = 510000; struct Tree { int a[maxn]; int n; void build(int _n) { n = _n; for (int i = 0; i < n; ++i) { a[i] = 0; } } void add(int x, int toadd) { for (; x < n; x |= (x + 1)) { a[x] += toadd; } } int get(int x) { int res = 0; for (; x >= 0; x = (x & (x + 1)) - 1) { res += a[x]; } return res; } } tree1; int fact[maxn]; void precalc() { fact[0] = 1; for (int i = 1; i < maxn; ++i) { fact[i] = mult(fact[i - 1], i); } } int a[maxn]; int n; int read() { if (scanf("%d", &n) < 1) { return 0; } for (int i = 0; i < n; ++i) { scanf("%d", a + i); --a[i]; } return 1; } int used[maxn]; int cnt[maxn]; void solve() { memset(used, 0, sizeof(used)); int zero = 0; for (int i = 0; i < n; ++i) { if (a[i] >= 0) { used[a[i]] = 1; } else { ++zero; } } cnt[0] = 0; for (int i = 0; i < n; ++i) { cnt[i + 1] = cnt[i] + !used[i]; } tree1.build(n); int res = 0; int zerobef = 0; long long total = 0; for (int i = n - 1; i >= 0; --i) { int cur = 0; if (a[i] >= 0) { add(cur, mult(fact[zero], tree1.get(a[i] - 1))); if (zero) { add(cur, mult(zerobef, mult(cnt[a[i]], fact[zero - 1]))); } tree1.add(a[i], 1); total += zero - cnt[a[i]]; } else { if (zero) { add(cur, mult(fact[zero - 1], total % mod)); } if (zero >= 2) { add(cur, mult(mult(zerobef, fact[zero - 2]), (long long) zero * (zero - 1) / 2 % mod)); } ++zerobef; } //eprintf("cur = %d\n", cur); add(res, mult(cur, fact[n - i - 1])); } add(res, fact[zero]); printf("%d\n", res); } int main() { precalc(); #ifdef LOCAL freopen(TASK ".out", "w", stdout); assert(freopen(TASK ".in", "r", stdin)); #endif while (1) { if (!read()) { break; } solve(); #ifdef DEBUG eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC); #endif } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Encyclopedia of Permutations |
User | XraY |
Language | C++14 (GCC 5.4.1) |
Score | 1200 |
Code Size | 2855 Byte |
Status | AC |
Exec Time | 94 ms |
Memory | 10240 KB |
Compile Error
./Main.cpp: In function ‘int read()’: ./Main.cpp:90:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", a + 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 | 9 ms | 4224 KB |
0_001.txt | AC | 9 ms | 4224 KB |
0_002.txt | AC | 9 ms | 4224 KB |
0_003.txt | AC | 9 ms | 4224 KB |
0_004.txt | AC | 9 ms | 4224 KB |
1_005.txt | AC | 9 ms | 4224 KB |
1_006.txt | AC | 9 ms | 4224 KB |
1_007.txt | AC | 9 ms | 4224 KB |
1_008.txt | AC | 9 ms | 4224 KB |
1_009.txt | AC | 9 ms | 4224 KB |
1_010.txt | AC | 9 ms | 4224 KB |
1_011.txt | AC | 9 ms | 4224 KB |
1_012.txt | AC | 9 ms | 4224 KB |
1_013.txt | AC | 9 ms | 4224 KB |
1_014.txt | AC | 9 ms | 4224 KB |
1_015.txt | AC | 9 ms | 4224 KB |
1_016.txt | AC | 9 ms | 4224 KB |
1_017.txt | AC | 9 ms | 4224 KB |
1_018.txt | AC | 9 ms | 4224 KB |
1_019.txt | AC | 9 ms | 4224 KB |
1_020.txt | AC | 9 ms | 4224 KB |
1_021.txt | AC | 9 ms | 4224 KB |
1_022.txt | AC | 9 ms | 4224 KB |
1_023.txt | AC | 9 ms | 4224 KB |
1_024.txt | AC | 9 ms | 4224 KB |
1_025.txt | AC | 9 ms | 4224 KB |
1_026.txt | AC | 9 ms | 4224 KB |
1_027.txt | AC | 9 ms | 4224 KB |
1_028.txt | AC | 9 ms | 4224 KB |
1_029.txt | AC | 9 ms | 4224 KB |
1_030.txt | AC | 9 ms | 4224 KB |
1_031.txt | AC | 9 ms | 4224 KB |
1_032.txt | AC | 9 ms | 4224 KB |
2_033.txt | AC | 56 ms | 10112 KB |
2_034.txt | AC | 32 ms | 7168 KB |
2_035.txt | AC | 65 ms | 10112 KB |
2_036.txt | AC | 61 ms | 9600 KB |
2_037.txt | AC | 73 ms | 10112 KB |
2_038.txt | AC | 64 ms | 9344 KB |
2_039.txt | AC | 75 ms | 10112 KB |
2_040.txt | AC | 41 ms | 7168 KB |
2_041.txt | AC | 79 ms | 10112 KB |
2_042.txt | AC | 21 ms | 5376 KB |
2_043.txt | AC | 82 ms | 10112 KB |
2_044.txt | AC | 57 ms | 8064 KB |
2_045.txt | AC | 85 ms | 10112 KB |
2_046.txt | AC | 81 ms | 9856 KB |
2_047.txt | AC | 87 ms | 10112 KB |
2_048.txt | AC | 42 ms | 6784 KB |
2_049.txt | AC | 93 ms | 10240 KB |
2_050.txt | AC | 61 ms | 8064 KB |
2_051.txt | AC | 90 ms | 10112 KB |
2_052.txt | AC | 82 ms | 9472 KB |
2_053.txt | AC | 56 ms | 10112 KB |
2_054.txt | AC | 94 ms | 10112 KB |
2_055.txt | AC | 78 ms | 10112 KB |
2_056.txt | AC | 77 ms | 10240 KB |
2_057.txt | AC | 70 ms | 10112 KB |