Submission #947117
Source Code Expand
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))
const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
const ll M = 1000000007;
ll kaijou[500010];
void init(){
kaijou[0] = 1;
rep1(i,500009){
kaijou[i] = kaijou[i-1] * i;
kaijou[i] %= M;
}
}
struct BIT{
int siz;
int s[1<<20+1];
void init(){
siz = 1<<20;
rep1(i,siz)s[i] = 0;
}
void add(int a){
while(a <= siz){
s[a] ++;
a += a&-a;
}
}
int sum(int a){
int ret = 0;
while(a > 0){
ret += s[a];
a -= a&-a;
}
return ret;
}
}bit;
int main(){
init();
bit.init();
static int n;
static int p[500010];
scanf("%d",&n);
rep(i,n)scanf("%d",&p[i]);
static int K[500010] = {} , cnt[500010] = {};
rep1(i,n)cnt[i] = 1;
rep(i,n){
K[i] = K[i-1];
if(p[i] == 0){
K[i] ++;
}
else {
cnt[p[i]] = 0;
}
}
K[n] = K[n-1];
rep1(i,500009)cnt[i] += cnt[i-1];
ll c=0,d=0,hoge = 0;
rep1(i,n){
if(cnt[i] > cnt[i-1]){
c += i-1;
d += cnt[i-1];
}
}
c *= K[n]-1;
c %= M;
d %= M;
ll ret = 0;
rep(i,n){
if(p[i] != 0){
ll _ret = 0;
_ret = kaijou[K[n]]*(p[i]-1-bit.sum(p[i])); _ret %= M;
_ret += M-( (kaijou[K[n]-1]*K[i])%M*cnt[p[i]] )%M;
_ret *= kaijou[n-i-1]; _ret %= M;
ret += _ret; ret %= M;
bit.add(p[i]);
hoge += K[n]-cnt[p[i]];
hoge %= M;
}
else {
ll _ret = c;
_ret +=M-( (K[n]-1)*hoge )%M;
_ret +=M-( d*((i==0)?0:K[i-1]) )%M;
_ret *= kaijou[n-i-1]; _ret %= M;
_ret *= (K[n] < 2)?0:kaijou[K[n]-2];
_ret %= M;
ret += _ret;
ret %= M;
}
/*else {
ll _ret = 0;
rep1(j,n){
if(cnt[j] == cnt[j-1])continue;
//cout << "__" << i << " " << j << endl;
ll __ret = 0;
__ret = kaijou[K[n]-1]*(j-1-bit.sum(j)); __ret %= M;
//cout << __ret << endl;
__ret += M-( (kaijou[K[n]-2]*((i==0)?0:K[i-1]))%M*cnt[j-1] )%M;
//cout << __ret << endl;
__ret *= kaijou[n-i-1]; __ret %= M;
//cout << __ret << endl;
_ret += __ret;
}
ret += _ret; ret %= M;
}*/
//cout << i << " " << ret << endl;
}
cout << (ret+kaijou[K[n]])%M << endl;
}
Submission Info
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:76:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:77:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i,n)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 |
16 ms |
10240 KB |
0_001.txt |
AC |
16 ms |
10240 KB |
0_002.txt |
AC |
16 ms |
10240 KB |
0_003.txt |
AC |
16 ms |
10240 KB |
0_004.txt |
AC |
16 ms |
10240 KB |
1_005.txt |
AC |
16 ms |
10240 KB |
1_006.txt |
AC |
16 ms |
10240 KB |
1_007.txt |
AC |
16 ms |
10240 KB |
1_008.txt |
AC |
16 ms |
10240 KB |
1_009.txt |
AC |
16 ms |
10240 KB |
1_010.txt |
AC |
16 ms |
10240 KB |
1_011.txt |
AC |
16 ms |
10240 KB |
1_012.txt |
AC |
16 ms |
10240 KB |
1_013.txt |
AC |
16 ms |
10240 KB |
1_014.txt |
AC |
16 ms |
10368 KB |
1_015.txt |
AC |
16 ms |
10240 KB |
1_016.txt |
AC |
16 ms |
10240 KB |
1_017.txt |
AC |
16 ms |
10240 KB |
1_018.txt |
AC |
16 ms |
10240 KB |
1_019.txt |
AC |
16 ms |
10240 KB |
1_020.txt |
AC |
16 ms |
10240 KB |
1_021.txt |
AC |
16 ms |
10240 KB |
1_022.txt |
AC |
16 ms |
10240 KB |
1_023.txt |
AC |
16 ms |
10240 KB |
1_024.txt |
AC |
16 ms |
10240 KB |
1_025.txt |
AC |
16 ms |
10240 KB |
1_026.txt |
AC |
16 ms |
10240 KB |
1_027.txt |
AC |
16 ms |
10240 KB |
1_028.txt |
AC |
16 ms |
10240 KB |
1_029.txt |
AC |
16 ms |
10240 KB |
1_030.txt |
AC |
16 ms |
10240 KB |
1_031.txt |
AC |
16 ms |
10240 KB |
1_032.txt |
AC |
16 ms |
10240 KB |
2_033.txt |
AC |
61 ms |
14080 KB |
2_034.txt |
AC |
39 ms |
12160 KB |
2_035.txt |
AC |
68 ms |
14080 KB |
2_036.txt |
AC |
65 ms |
13824 KB |
2_037.txt |
AC |
76 ms |
14080 KB |
2_038.txt |
AC |
70 ms |
13696 KB |
2_039.txt |
AC |
83 ms |
14080 KB |
2_040.txt |
AC |
49 ms |
12160 KB |
2_041.txt |
AC |
89 ms |
14080 KB |
2_042.txt |
AC |
29 ms |
11008 KB |
2_043.txt |
AC |
94 ms |
14080 KB |
2_044.txt |
AC |
67 ms |
12800 KB |
2_045.txt |
AC |
98 ms |
14080 KB |
2_046.txt |
AC |
95 ms |
13952 KB |
2_047.txt |
AC |
103 ms |
14080 KB |
2_048.txt |
AC |
54 ms |
11904 KB |
2_049.txt |
AC |
107 ms |
14080 KB |
2_050.txt |
AC |
75 ms |
12800 KB |
2_051.txt |
AC |
113 ms |
14080 KB |
2_052.txt |
AC |
103 ms |
13696 KB |
2_053.txt |
AC |
63 ms |
14080 KB |
2_054.txt |
AC |
112 ms |
14080 KB |
2_055.txt |
AC |
98 ms |
14080 KB |
2_056.txt |
AC |
96 ms |
14080 KB |
2_057.txt |
AC |
79 ms |
14080 KB |