Submission #1696226
Source Code Expand
#include <bits/stdc++.h> // iostream is too mainstream #include <cstdio> // bitch please #include <iostream> #include <algorithm> #include <cstdlib> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <list> #include <cmath> #include <iomanip> #include <time.h> #define dibs reserve #define OVER9000 1234567890123456789LL #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++) #define tisic 47 #define soclose 1e-8 #define chocolate win // so much chocolate #define patkan 9 #define ff first #define ss second #define abs(x) ((x < 0)?-(x):x) #define uint unsigned int #define dbl long double #define pi 3.14159265358979323846 using namespace std; // mylittledoge typedef long long cat; #ifdef DONLINE_JUDGE // palindromic tree is better than splay tree! #define lld I64d #endif cat mod =1000000007; struct intervalac { struct node { int son[2]; int z, k, sum0; cat sum, sum2, add; }; vector<node> T; void constI(int akt, vector<int> &D) { node n =T[akt]; if(n.k-n.z == 1) { T[akt].sum0 =(D[n.z] == 0); return; } for(int i =0; i < 2; i++) { if(i == 0) n.k =(n.z+n.k)/2; else {n.z =n.k; n.k =T[akt].k;} T[akt].son[i] =T.size(); T.push_back(n); constI(T.size()-1, D); } T[akt].sum0 =T[T[akt].son[0]].sum0+T[T[akt].son[1]].sum0; } intervalac(int N, vector<int> &D) { node n; n.z =n.sum =n.add =n.sum0 =n.sum2 =0; n.k =N; n.son[0] =n.son[1] =-1; T.resize(1,n); constI(0,D); } void upd(int akt) { if(T[akt].add == 0) return; node n =T[akt]; T[akt].sum +=n.sum0*n.add; T[akt].sum2 +=(n.k-n.z-n.sum0)*n.add; for(int i =0; i < 2; i++) if(n.son[i] != -1) T[n.son[i]].add +=n.add; T[akt].add =0; } void put(int akt, int zac, int kon, cat val) { upd(akt); node n =T[akt]; if(n.k <= zac || kon <= n.z) return; if(n.z == zac && n.k == kon) { T[akt].add +=val; upd(akt); return; } put(n.son[0],zac,min(kon,(n.z+n.k)/2),val); put(n.son[1],max(zac,(n.z+n.k)/2),kon,val); T[akt].sum =T[n.son[0]].sum+T[n.son[1]].sum; T[akt].sum2 =T[n.son[0]].sum2+T[n.son[1]].sum2; } cat get(int akt, int zac, int kon, int tp) { upd(akt); node n =T[akt]; if(n.k <= zac || kon <= n.z) return 0; if(n.z == zac && n.k == kon) { if(tp == 0) return n.sum; return n.sum2; } return get(n.son[0],zac,min(kon,(n.z+n.k)/2),tp) + get(n.son[1],max(zac,(n.z+n.k)/2),kon,tp); } }; int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int N; cin >> N; vector<int> P(N), D(N,0); for(int i =0; i < N; i++) { cin >> P[i]; P[i]--; if(P[i] >= 0) D[P[i]]++; } vector<cat> fac(N+1,1); for(int i =1; i <= N; i++) fac[i] =(fac[i-1]*i)%mod; int n =0; for(int i =0; i < N; i++) if(D[i] == 0) n++; cat ans =fac[n]; intervalac I(N,D); for(int i =N-1; i >= 0; i--) { if(P[i] == -1) ans +=fac[N-1-i]*fac[n-1]%mod*(I.get(0,0,N,0)%mod)%mod; else ans +=fac[N-1-i]*fac[n]%mod*(I.get(0,P[i],P[i]+1,1)%mod)%mod; if(P[i] >= 0) I.put(0,P[i]+1,N,1); } vector<int> less(N,0); for(int i =0; i < N; i++) if(D[i] == 0) less[i] =1; for(int i =1; i < N; i++) less[i] +=less[i-1]; // fac * ( sum_k k * C(n_lt, k) * C(n_gt, n_r-k) ) * n_r! * n_l! = fac * n_l * n! / 2 int l =0; cat inv2 =(mod+1)/2; for(int i =N-1; i >= 0; i--) { if(P[i] == -1) ans +=fac[n]*fac[N-1-i]%mod*l%mod*inv2%mod; else ans +=less[P[i]]*fac[n-1]%mod*fac[N-1-i]%mod*l%mod; if(P[i] == -1) l++; } ans %=mod; if(ans < 0) ans +=mod; cout << ans << "\n"; return 0;} // look at my code // my code is amazing
Submission Info
Submission Time | |
---|---|
Task | E - Encyclopedia of Permutations |
User | xellos |
Language | C++14 (GCC 5.4.1) |
Score | 1200 |
Code Size | 3728 Byte |
Status | AC |
Exec Time | 833 ms |
Memory | 59364 KB |
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 | 1 ms | 256 KB |
0_001.txt | AC | 1 ms | 256 KB |
0_002.txt | AC | 1 ms | 256 KB |
0_003.txt | AC | 1 ms | 256 KB |
0_004.txt | AC | 1 ms | 256 KB |
1_005.txt | AC | 1 ms | 256 KB |
1_006.txt | AC | 1 ms | 256 KB |
1_007.txt | AC | 1 ms | 256 KB |
1_008.txt | AC | 2 ms | 832 KB |
1_009.txt | AC | 2 ms | 640 KB |
1_010.txt | AC | 3 ms | 832 KB |
1_011.txt | AC | 2 ms | 832 KB |
1_012.txt | AC | 3 ms | 832 KB |
1_013.txt | AC | 2 ms | 512 KB |
1_014.txt | AC | 3 ms | 832 KB |
1_015.txt | AC | 2 ms | 576 KB |
1_016.txt | AC | 3 ms | 832 KB |
1_017.txt | AC | 1 ms | 256 KB |
1_018.txt | AC | 3 ms | 832 KB |
1_019.txt | AC | 2 ms | 576 KB |
1_020.txt | AC | 3 ms | 832 KB |
1_021.txt | AC | 2 ms | 576 KB |
1_022.txt | AC | 3 ms | 832 KB |
1_023.txt | AC | 3 ms | 640 KB |
1_024.txt | AC | 4 ms | 832 KB |
1_025.txt | AC | 2 ms | 256 KB |
1_026.txt | AC | 4 ms | 832 KB |
1_027.txt | AC | 3 ms | 576 KB |
1_028.txt | AC | 2 ms | 832 KB |
1_029.txt | AC | 4 ms | 832 KB |
1_030.txt | AC | 3 ms | 832 KB |
1_031.txt | AC | 3 ms | 832 KB |
1_032.txt | AC | 3 ms | 832 KB |
2_033.txt | AC | 127 ms | 59236 KB |
2_034.txt | AC | 62 ms | 28904 KB |
2_035.txt | AC | 209 ms | 58468 KB |
2_036.txt | AC | 194 ms | 57956 KB |
2_037.txt | AC | 298 ms | 58212 KB |
2_038.txt | AC | 254 ms | 58212 KB |
2_039.txt | AC | 369 ms | 57956 KB |
2_040.txt | AC | 164 ms | 30696 KB |
2_041.txt | AC | 434 ms | 58084 KB |
2_042.txt | AC | 59 ms | 14444 KB |
2_043.txt | AC | 505 ms | 58980 KB |
2_044.txt | AC | 324 ms | 55524 KB |
2_045.txt | AC | 588 ms | 57828 KB |
2_046.txt | AC | 561 ms | 57956 KB |
2_047.txt | AC | 640 ms | 59364 KB |
2_048.txt | AC | 236 ms | 28520 KB |
2_049.txt | AC | 748 ms | 57444 KB |
2_050.txt | AC | 466 ms | 56676 KB |
2_051.txt | AC | 795 ms | 58724 KB |
2_052.txt | AC | 759 ms | 57828 KB |
2_053.txt | AC | 127 ms | 57700 KB |
2_054.txt | AC | 833 ms | 57572 KB |
2_055.txt | AC | 378 ms | 58340 KB |
2_056.txt | AC | 377 ms | 58468 KB |
2_057.txt | AC | 267 ms | 58596 KB |