Submission #946419

---

Source Code Expand

/**
 *    author:  [itmo] enot.1.10
 *    created: 23.10.2016 15:26:20       
**/
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define mp make_pair
#define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),a.end()
#define pw(x) (1LL<<(x))

using namespace std;

typedef long long ll;
typedef double dbl;
typedef vector<int> vi;
typedef pair<int, int> pi;

const int inf = 1.01e9;
const dbl eps = 1e-9;

/* --- main part --- */

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


int a[N];
int u[N];
int b[N], bc = 0;

int fact[N];
int rfact[N];

int t[N];

inline void upd(int x, int dx)
{
    x++;
    for (; x < N; x += x & -x) t[x] += dx;
}

inline int get(int x)
{
    x++;
    int res = 0;
    for (; x > 0; x -= x & -x) res += t[x];
    return res;
}

int t2[N];

inline void upd2(int x, int dx)
{
    x++;
    for (; x < N; x += x & -x) t2[x] += dx;
}

inline int get2(int x)
{             
    x++;
    int res = 0;
    for (; x > 0; x -= x & -x) res += t2[x];
    return res;
}

int rev(int x, int m)
{
    if (x == 1) return 1;
    return (1 - rev(m % x, x) * (ll)m) / x + m;
}

int cnk(int n, int k)
{
    return fact[n] * (ll)rfact[k] % mod * rfact[n - k] % mod;
}

int main()
{
    #ifdef home
        assert(freopen("1.in", "r", stdin));
        assert(freopen("1.out", "w", stdout));
    #endif
    fact[0] = 1;
    for (int i = 1; i < N; ++i) fact[i] = fact[i - 1] * (ll)i % mod;
    for (int i = 0; i < N; ++i) rfact[i] = rev(fact[i], mod);

    int res = 0;
    int n;
    scanf("%d", &n);
    forn(i, n) scanf("%d", a + i);
    forn(i, n) a[i]--;
    forn(i, n) if (a[i] != -1) u[a[i]] = 1;
    forn(i, n) if (!u[i]) b[bc++] = i;

    forn(i, n) if (!u[i]) upd2(n - i, 1);

    int sumless = 0;
    int f = 0;    
    for (int i = n - 1; i >= 0; --i)
    {
        if (a[i] >= 0)
        {
            int lss = get(a[i]);
            //for (int j = i + 1; j < n; ++j) if (a[j] != -1 && a[j] < a[i]) lss++;
            int big = get2(n - a[i]);
            int small = bc - big;
            int val = cnk(bc, f) * (ll)lss % mod;
            if (bc >= 1 && f > 0) val = (val + cnk(bc - 1, f - 1) * (ll)small) % mod;
            res = (res + val * (ll)fact[f] % mod * (ll)fact[bc - f] % mod * fact[n - i - 1]) % mod;
            upd(a[i], 1);
            sumless = (sumless + get2(n - a[i])) % mod;
        }
        else
        {
            int add = 0;

            int sum = bc * (ll)(bc - 1) % mod * rev(2, mod) % mod;
            int val = cnk(bc - 1, f) * (ll)sumless % mod;
            if (bc >= 2 && f > 0) val = (val + cnk(bc - 2, f - 1) * (ll)sum) % mod;
            
            res = (res + val * (ll)fact[f] % mod * fact[bc - 1 - f] % mod * fact[n - i - 1]) % mod;
            f++;
        }
    }
    res = (res + fact[bc]) % mod;
    printf("%d\n", res);
            
    #ifdef home
        eprintf("time = %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC));
    #endif
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:96:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:97:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     forn(i, n) scanf("%d", a + i);
                                  ^

Judge Result