Submission #368053

#	Time	Username	Problem	Language	Result	Execution time	Memory
368053		ncduy0303	Cryptography (NOI20_crypto)	C++17	35 / 100	341 ms	20812 KiB

Crypto

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

#define ll long long
#define ar array

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void solve() {
    int n; cin >> n;
    vector<ll> fact(n);
    fact[0] = 1;
    for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i % MOD;
    vector<ar<int,2>> a(n);
    for (int i = 0; i < n; i++) cin >> a[i][0], a[i][1] = i;
    sort(a.begin(), a.end());
    vector<int> b(n);
    for (int i = 0; i < n; i++) b[a[i][1]] = i;
    // for (int x : b) cerr << x << " ";
    // cerr << "\n";
    ll ans = 0;
    ordered_set<int> os;
    for (int i = 0; i < n; i++) {
        os.insert(b[i]);
        ll tmp = fact[n - i - 1] * (b[i] - os.order_of_key(b[i])) % MOD;
        // cerr << tmp << " ";
        ans = (ans + tmp) % MOD; 
    }
    // cerr << "\n";
    cout << ans + 1 << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
}

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