Submission #1535461


Source Code Expand

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll mod = 1000*1000*1000+7;

vector<ll> fact;
int N, K;
vector<int> P;

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4*N, 0);
    }
    void upd(int idx, int val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n] = val;
            return;
        }
        int m = (l + r)>>1;
        upd(idx, val, l, m, 2*n);
        upd(idx, val, m + 1, r, 2*n + 1);
        tree[n] = tree[2*n] + tree[2*n + 1];
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 0;
        if(a <= l && r <= b) return tree[n];
        int m = (l + r)>>1;
        int L = quer(a, b, l, m, 2*n);
        int R = quer(a, b, m + 1, r, 2*n + 1);
        return L + R;
    }
} bit, sub;

int main() {
    fact.resize(500010);
    fact[0] = 1;
    for(int i = 1; i < 500010; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }

    scanf("%d", &N);
    K = 0;
    P.resize(N);
    sub.init();
    for(int i = 0; i < N; i++) {
        scanf("%d", &P[i]);
        P[i]--;
        if(P[i] == -1) K++;
        sub.upd(i, 1, 0, N - 1, 1);
    }

    ll sum = 1LL * N * (N - 1) / 2;
    for(int i = 0; i < N; i++) {
        if(P[i] != -1) sum -= P[i], sub.upd(P[i], 0, 0, N - 1, 1);
    }
    sum = (sum % mod + mod) % mod;

    bit.init();
    ll ans = 0;
    ll tmp = 0;
    int cnt = 0;
    for(int i = 0; i < N; i++) {
        if(P[i] == -1) {
            ll a = sum * fact[K - 1] % mod;
            ll b = tmp * fact[K - 1] % mod;
            ll c = K < 2? 0 : (1LL * K * (K - 1) / 2 % mod) * fact[K - 2] % mod * cnt % mod;

            ans += (a - b - c) * fact[N - i - 1] % mod, ans = (ans % mod + mod) % mod;

            cnt++;
        }
        else {
            bit.upd(P[i], 1, 0, N - 1, 1);
            tmp += sub.quer(P[i] + 1, N - 1, 0, N - 1, 1);
            tmp %= mod;

            ll a = fact[K] * P[i] % mod;
            ll b = fact[K] * bit.quer(0, P[i] - 1, 0, N - 1, 1) % mod;
            ll c = K == 0? 0 : fact[K - 1] * sub.quer(0, P[i] - 1, 0, N - 1, 1) % mod * cnt % mod;

            ans += (a - b - c) * fact[N - 1 - i] % mod, ans = (ans % mod + mod) % mod;
        }
    }
    cout << (ans + fact[K]) % mod;
}

Submission Info

Submission Time
Task E - Encyclopedia of Permutations
User choikiwon
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 2391 Byte
Status AC
Exec Time 519 ms
Memory 21760 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:45:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
./Main.cpp:50:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &P[i]);
                           ^

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 6 ms 4096 KB
0_001.txt AC 6 ms 4096 KB
0_002.txt AC 6 ms 4096 KB
0_003.txt AC 6 ms 4096 KB
0_004.txt AC 6 ms 4096 KB
1_005.txt AC 6 ms 4096 KB
1_006.txt AC 6 ms 4096 KB
1_007.txt AC 6 ms 4096 KB
1_008.txt AC 6 ms 4224 KB
1_009.txt AC 6 ms 4224 KB
1_010.txt AC 6 ms 4224 KB
1_011.txt AC 6 ms 4224 KB
1_012.txt AC 7 ms 4224 KB
1_013.txt AC 6 ms 4224 KB
1_014.txt AC 7 ms 4224 KB
1_015.txt AC 6 ms 4224 KB
1_016.txt AC 7 ms 4224 KB
1_017.txt AC 6 ms 4096 KB
1_018.txt AC 7 ms 4224 KB
1_019.txt AC 6 ms 4224 KB
1_020.txt AC 8 ms 4224 KB
1_021.txt AC 7 ms 4224 KB
1_022.txt AC 7 ms 4224 KB
1_023.txt AC 7 ms 4224 KB
1_024.txt AC 8 ms 4224 KB
1_025.txt AC 6 ms 4096 KB
1_026.txt AC 7 ms 4224 KB
1_027.txt AC 6 ms 4224 KB
1_028.txt AC 6 ms 4224 KB
1_029.txt AC 8 ms 4224 KB
1_030.txt AC 7 ms 4224 KB
1_031.txt AC 7 ms 4224 KB
1_032.txt AC 7 ms 4224 KB
2_033.txt AC 102 ms 21760 KB
2_034.txt AC 53 ms 12928 KB
2_035.txt AC 157 ms 21760 KB
2_036.txt AC 141 ms 20352 KB
2_037.txt AC 213 ms 21760 KB
2_038.txt AC 177 ms 19584 KB
2_039.txt AC 255 ms 21760 KB
2_040.txt AC 123 ms 12928 KB
2_041.txt AC 303 ms 21760 KB
2_042.txt AC 62 ms 7552 KB
2_043.txt AC 354 ms 21760 KB
2_044.txt AC 226 ms 15744 KB
2_045.txt AC 399 ms 21760 KB
2_046.txt AC 375 ms 20992 KB
2_047.txt AC 434 ms 21760 KB
2_048.txt AC 183 ms 11904 KB
2_049.txt AC 477 ms 21760 KB
2_050.txt AC 313 ms 15744 KB
2_051.txt AC 430 ms 21760 KB
2_052.txt AC 389 ms 20096 KB
2_053.txt AC 102 ms 21760 KB
2_054.txt AC 519 ms 21760 KB
2_055.txt AC 304 ms 21760 KB
2_056.txt AC 302 ms 21760 KB
2_057.txt AC 240 ms 21760 KB