Submission #949982
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N; int P[505050]; int D[505050]; int S[505050]; int Z[505050]; int ZL[505050]; ll fact[505050]; ll mo=1000000007; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<int,20> bt; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) D[i]=1; FOR(i,N) { cin>>P[i]; P[i]--; if(P[i]>=0) D[P[i]]--; else Z[i]++; } FOR(i,N) { S[i]=(i?S[i-1]:0)+D[i]; ZL[i]=(i?ZL[i-1]:0)+Z[i]; } fact[0]=1; FOR(i,505000) fact[i+1]=fact[i]*(i+1)%mo; ll T=0; ll TZ=0; FOR(i,N) if(D[i]==1) T=(T+i)%mo; int K=ZL[N-1]; ll ret=fact[K]; FOR(i,N) { ll pat; if(P[i]>=0) { pat = fact[K]*P[i]%mo; pat += (i?ZL[i-1]:0)*(mo-S[P[i]]*fact[K-1]%mo)%mo; pat += bt(P[i])*(mo-fact[K])%mo; bt.add(P[i],1); (TZ += S[N-1]-S[P[i]])%=mo; } else { pat = T*fact[K-1]%mo; pat += (i?ZL[i-1]:0)*(mo-1LL*K*(K-1)/2%mo*fact[K-2]%mo)%mo; pat += mo-TZ*fact[K-1]%mo; } ret += pat%mo*fact[N-1-i]%mo; } cout<<ret%mo<<endl; } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false), cin.tie(0); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Encyclopedia of Permutations |
User | kmjp |
Language | C++14 (GCC 5.4.1) |
Score | 1200 |
Code Size | 1855 Byte |
Status | AC |
Exec Time | 140 ms |
Memory | 16000 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 | 14 ms | 4224 KB |
0_001.txt | AC | 14 ms | 4224 KB |
0_002.txt | AC | 14 ms | 4224 KB |
0_003.txt | AC | 14 ms | 4224 KB |
0_004.txt | AC | 14 ms | 4224 KB |
1_005.txt | AC | 14 ms | 4224 KB |
1_006.txt | AC | 14 ms | 4224 KB |
1_007.txt | AC | 14 ms | 4224 KB |
1_008.txt | AC | 14 ms | 4352 KB |
1_009.txt | AC | 14 ms | 4352 KB |
1_010.txt | AC | 14 ms | 4352 KB |
1_011.txt | AC | 14 ms | 4352 KB |
1_012.txt | AC | 14 ms | 4352 KB |
1_013.txt | AC | 14 ms | 4224 KB |
1_014.txt | AC | 14 ms | 4352 KB |
1_015.txt | AC | 14 ms | 4352 KB |
1_016.txt | AC | 14 ms | 4352 KB |
1_017.txt | AC | 14 ms | 4224 KB |
1_018.txt | AC | 14 ms | 4352 KB |
1_019.txt | AC | 14 ms | 4352 KB |
1_020.txt | AC | 14 ms | 4352 KB |
1_021.txt | AC | 14 ms | 4352 KB |
1_022.txt | AC | 14 ms | 4352 KB |
1_023.txt | AC | 14 ms | 4352 KB |
1_024.txt | AC | 14 ms | 4352 KB |
1_025.txt | AC | 14 ms | 4224 KB |
1_026.txt | AC | 14 ms | 4352 KB |
1_027.txt | AC | 14 ms | 4224 KB |
1_028.txt | AC | 14 ms | 4352 KB |
1_029.txt | AC | 14 ms | 4352 KB |
1_030.txt | AC | 14 ms | 4352 KB |
1_031.txt | AC | 14 ms | 4352 KB |
1_032.txt | AC | 14 ms | 4352 KB |
2_033.txt | AC | 102 ms | 14080 KB |
2_034.txt | AC | 57 ms | 9088 KB |
2_035.txt | AC | 111 ms | 16000 KB |
2_036.txt | AC | 102 ms | 14976 KB |
2_037.txt | AC | 115 ms | 16000 KB |
2_038.txt | AC | 102 ms | 14464 KB |
2_039.txt | AC | 121 ms | 16000 KB |
2_040.txt | AC | 67 ms | 10112 KB |
2_041.txt | AC | 126 ms | 16000 KB |
2_042.txt | AC | 34 ms | 6528 KB |
2_043.txt | AC | 129 ms | 16000 KB |
2_044.txt | AC | 89 ms | 11904 KB |
2_045.txt | AC | 132 ms | 16000 KB |
2_046.txt | AC | 127 ms | 15488 KB |
2_047.txt | AC | 135 ms | 16000 KB |
2_048.txt | AC | 66 ms | 9472 KB |
2_049.txt | AC | 140 ms | 16000 KB |
2_050.txt | AC | 93 ms | 11904 KB |
2_051.txt | AC | 137 ms | 13952 KB |
2_052.txt | AC | 125 ms | 13056 KB |
2_053.txt | AC | 101 ms | 13952 KB |
2_054.txt | AC | 138 ms | 13952 KB |
2_055.txt | AC | 117 ms | 13952 KB |
2_056.txt | AC | 117 ms | 13952 KB |
2_057.txt | AC | 115 ms | 16000 KB |