Submission #1249630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249630		ndquang	Cryptography (NOI20_crypto)	C++20	59 / 100	307 ms	28616 KiB

Crypto

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

/** Author: Nguyen Duy Quang **/

#define test int T; cin >> T; while(T--)
#define all(x) (x).begin(), (x).end()
#define Bit(x, y) ((x >> y) & 1)
#define int long long
#define pb push_back
#define fi first
#define sc second
#define inpFile(Task) freopen(Task".inp", "r", stdin);
#define outFile(Task) freopen(Task".out", "w", stdout);
#define submitFile(Task) inpFile(Task); outFile(Task);

using pii = pair<int, int>;
using ull = unsigned long long;
const int INF = (int)1e18, MOD1 = (int)1e9 + 7, MOD2 = (int)998244353;
template<class X, class Y> void maximize(X &a, const Y &b) { a = (a < b) ? b : a; }
template<class X, class Y> void minimize(X &a, const Y &b) { a = (a > b) ? b : a; }
template<class T> void add(T& a, T b) { a += b; if(a >= MOD1) a -= MOD1; }
template<class T> void sub(T& a, T b) { a -= b; if(a <= 0) a += MOD1; }

///END OF TEMPLATE

const int maxn = (int)3e5 + 8;

int n, p[maxn];
int a[maxn], fac[maxn], bit[maxn];
map<int, int> compress;

void update(int idx) {
    while(idx < maxn) {
        bit[idx]++;
        idx += idx & -idx;
    }
}

int get(int idx) {
    int res = 0;
    while(idx > 0) {
        res += bit[idx];
        idx -= idx & -idx;
    }
    return res;
}

signed main() {
    cin.tie(0)->ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
        a[i] = p[i];
    }
    sort(a + 1, a + n + 1);
    int cnt = 1;
    for(int i = 1; i <= n; i++)
        if(!compress.count(a[i])) compress[a[i]] = cnt++;
    for(int i = 1; i <= n; i++) p[i] = compress[p[i]];
    fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = (fac[i - 1] * i) % MOD1;
    int res = 0;
    for(int i = 1; i <= n; i++) {
        int x = p[i];
        add(res, (x - 1 - get(x - 1)) * fac[n - i]);
        update(x);
    }
    res++;
    cout << res % MOD1;
    return 0;
}

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