Submission #946212


Source Code Expand

// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
    freopen(name ".in","r",stdin); \
    freopen(name ".out","w",stdout); \
} while (0)
#endif

// }}}

template<typename T>
struct BIT {
    int n;
    vector<T> a;
    void init(int _n) {
        n = _n;
        a.resize(n + 1);
        a.clear();
    }
    void ins(int x, T v) {
        for (int i = x; i <= n; i += i & -i) {
            a[i] += v;
        }
    }
    T ask(int x) {
        T s = 0;
        for (int i = x; i; i -= i & -i) {
            s += a[i];
        }
        return s;
    }
    T ask(int l, int r) {
        auto s = ask(r);
        if (l > 0) {
            s += ask(l - 1);
        }
        return s;
    }
};

BIT<int> bit;

const int N=5e5+10;
const LL MOD=1e9+7;

int inv[N],fac[N],ifac[N];
void predo() {
	inv[1]=1;
	REP1(i,2,N-1) inv[i]=1LL*inv[MOD%i]*(MOD-MOD/i)%MOD;
	fac[0]=fac[1]=ifac[0]=ifac[1]=1;
	REP1(i,2,N-1) fac[i]=1LL*fac[i-1]*i%MOD;
	REP1(i,2,N-1) ifac[i]=1LL*ifac[i-1]*inv[i]%MOD;
}

LL C( int n, int m ) {
    if ( m>n ) return 0;
    return 1LL*fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;
}

int n,a[N],c[N],gt[N];
LL sgt[N];
int main() {
    predo();
    R(n);
    REP1(i,1,n) R(a[i]);
    REP1(i,1,n) if ( a[i] ) c[a[i]]++;
    REP1(i,1,n) c[i]+=c[i-1];
    LL sz=0;
    REP1(i,1,n) if ( a[i]==0 ) sz++;
    REP1(i,1,n) if ( a[i] ) {
        int lt=a[i]-c[a[i]];
        gt[i]=sz-lt;
    }
    for ( int i=n; i>=1; i-- ) sgt[i]=(sgt[i+1]+gt[i])%MOD;
    bit.init(n);
    REP1(i,1,n) if ( a[i] ) bit.ins(a[i],1);
    LL ans=0;
    LL z=sz;
    REP1(i,1,n) {
        LL e;
        if ( a[i]==0 ) {
            z--;
            e=z*inv[2]%MOD;
            e=(e+sgt[i]*inv[sz])%MOD;
        } else {
            bit.ins(a[i],-1);
            LL base=bit.ask(a[i]);
            if ( z==0 ) {
                e=base;
            } else {
                LL lt=a[i]-c[a[i]];
                e=(base+lt*inv[sz]%MOD*z)%MOD;
            }
        }
        LL now=e*fac[sz]%MOD;
        now=now*fac[n-i]%MOD;
        ans+=now;
        dump(i,a[i],e*fac[sz]%MOD,now);
    }
    ans+=fac[sz];
    ans%=MOD;
    W(ans);
    return 0;
}

Submission Info

Submission Time
Task E - Encyclopedia of Permutations
User shik
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 4899 Byte
Status AC
Exec Time 137 ms
Memory 17920 KB

Compile Error

./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:46: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                              ^
./Main.cpp: In function ‘void _R(int&)’:
./Main.cpp:61:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( int &x ) { scanf("%d",&x); }
                                   ^
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                               ^
./Main.cpp: In function ‘void _R(double&)’:
./Main.cpp:63:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-resu...

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 500 / 500 700 / 700
Status
AC × 5
AC × 33
AC × 58
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 24 ms 6144 KB
0_001.txt AC 24 ms 6144 KB
0_002.txt AC 24 ms 6144 KB
0_003.txt AC 24 ms 6144 KB
0_004.txt AC 24 ms 6144 KB
1_005.txt AC 24 ms 6144 KB
1_006.txt AC 24 ms 6144 KB
1_007.txt AC 24 ms 6144 KB
1_008.txt AC 24 ms 6144 KB
1_009.txt AC 24 ms 6144 KB
1_010.txt AC 24 ms 6144 KB
1_011.txt AC 24 ms 6144 KB
1_012.txt AC 25 ms 6144 KB
1_013.txt AC 24 ms 6144 KB
1_014.txt AC 25 ms 6144 KB
1_015.txt AC 24 ms 6144 KB
1_016.txt AC 24 ms 6144 KB
1_017.txt AC 24 ms 6144 KB
1_018.txt AC 25 ms 6144 KB
1_019.txt AC 24 ms 6144 KB
1_020.txt AC 25 ms 6144 KB
1_021.txt AC 24 ms 6144 KB
1_022.txt AC 25 ms 6144 KB
1_023.txt AC 24 ms 6144 KB
1_024.txt AC 25 ms 6144 KB
1_025.txt AC 24 ms 6144 KB
1_026.txt AC 25 ms 6144 KB
1_027.txt AC 24 ms 6144 KB
1_028.txt AC 24 ms 6144 KB
1_029.txt AC 25 ms 6144 KB
1_030.txt AC 25 ms 6144 KB
1_031.txt AC 25 ms 6144 KB
1_032.txt AC 24 ms 6144 KB
2_033.txt AC 79 ms 15872 KB
2_034.txt AC 52 ms 11008 KB
2_035.txt AC 89 ms 17792 KB
2_036.txt AC 83 ms 16896 KB
2_037.txt AC 97 ms 17792 KB
2_038.txt AC 88 ms 16384 KB
2_039.txt AC 106 ms 17920 KB
2_040.txt AC 64 ms 11904 KB
2_041.txt AC 112 ms 17792 KB
2_042.txt AC 40 ms 8320 KB
2_043.txt AC 117 ms 17792 KB
2_044.txt AC 85 ms 13824 KB
2_045.txt AC 122 ms 17792 KB
2_046.txt AC 118 ms 17280 KB
2_047.txt AC 127 ms 17792 KB
2_048.txt AC 67 ms 11264 KB
2_049.txt AC 131 ms 17792 KB
2_050.txt AC 93 ms 13824 KB
2_051.txt AC 130 ms 17792 KB
2_052.txt AC 119 ms 16640 KB
2_053.txt AC 80 ms 15872 KB
2_054.txt AC 137 ms 17792 KB
2_055.txt AC 110 ms 17792 KB
2_056.txt AC 110 ms 17792 KB
2_057.txt AC 98 ms 17792 KB