Submission #492562

#	Time	Username	Problem	Language	Result	Execution time	Memory
492562		anonymous	Cryptography (NOI20_crypto)	C++14	100 / 100	127 ms	9164 KiB

Crypto

#include <iostream>
#include <algorithm>
#define MAXN 300005
#define LL long long
#define MOD 1000000007
using namespace std;

int N,P[MAXN], Lookup[MAXN];
LL fac[MAXN]={1}, ans;

class Fenwick {
    int BIT[MAXN];
public:
    void upd(int x) {
        for (; x<=N; x+= x&(-x)) {BIT[x]++;}
    }
    LL ask(int p) {
        int res = 0;
        for (; p>0; p-=p&(-p)) {res += BIT[p];}
        return res;
    }
} FT;

int main() {
    //freopen("cryptin.txt","r",stdin);
    scanf("%d",&N);
    for (LL i=1; i<=N; i++) {
        scanf("%d",&P[i]);
        Lookup[i] = P[i];
        fac[i] = (i*fac[i-1]) % MOD;
    }
    sort(Lookup+1, Lookup+N+1);
    for (int i=1; i<=N; i++) {
        LL ord = lower_bound(Lookup+1, Lookup+N+1, P[i]) - Lookup;
        ans = (ans + fac[N-i]*(ord-1-FT.ask(ord))) % MOD;
        FT.upd(ord);
    }
    printf("%lld", (ans+1) % MOD);
}

Compilation message (stderr)

Crypto.cpp: In function 'int main()':
Crypto.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
Crypto.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d",&P[i]);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 9 / 9
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 21 / 21
• Subtask 6: 13 / 13
• Subtask 7: 19 / 19
• Subtask 8: 12 / 12