Submission #946114

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int mod = 1e9 + 7;

inline int add(int a, int b) {
  return a+b >= mod ? a+b-mod : a+b;
}

inline int sub(int a, int b) {
  return a >= b ? a-b : a-b+mod;
}

inline int mul(int a, int b) {
  return llint(a)*b % mod;
}

const int MAX = 500050;

int f[MAX];
int P[MAX];

int L[MAX];

int sum(int x) {
  int r = 0;
  for (++x; x; x -= x&-x)
    r += L[x];
  return r;
}

void addv(int x, int v) {
  for (++x; x < MAX; x += x&-x)
    L[x] += v;
}

bool ima[MAX];
int ls[MAX];
int G[MAX];

int main(void) {
  int N;
  scanf("%d", &N);
  REP(i, N) scanf("%d", &P[i]);

  f[0] = 1;
  REP(i, N) f[i+1] = mul(f[i], i+1);

  int F = 0;
  REP(i, N) {
    F += P[i] == 0;
    ima[P[i]] = true;
  }

  ls[0] = 0;
  for (int i = 1; i <= N; ++i)
    ls[i] = ls[i-1] + !ima[i];
  
  int ans = f[F];
  int L = 0;

  int gg = 0;
  for (int i = N-1; i >= 0; --i) {
    if (P[i]) {
      gg = add(gg, F -  ls[P[i]]);
    } else {
      G[i] = gg;
    }
  }
  REP(i, N) {
    int total = 0;
    if (P[i]) {
      int FL = P[i]-1 - sum(P[i]) - ls[P[i]];
      total = add(total, mul(FL, f[F]));

      if (F > 0) {
        total = add(total, mul(mul(ls[P[i]], F-L), f[F-1]));
      }
      addv(P[i], 1);
    } else {
      L++;
      if (F > 1) {
        int pairs = ((llint(F) * (F - 1)) / 2) % mod;
        total = add(total, mul(pairs, mul(F-L, f[F-2])));
      }
      total = add(total, mul(G[i], f[F-1]));
    }

    ans = add(ans, mul(total, f[N-i-1]));
  }

  printf("%d\n", ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:54:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
                  ^
./Main.cpp:55:31: 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