제출 #337524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337524		ncduy0303	Cryptography (NOI20_crypto)	C++17	100 / 100	378 ms	23404 KiB

Crypto

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

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

#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_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class K, class V> using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

vector<ll> fact;

void precompute(int n) {
    fact.assign(n + 1, 1); 
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
}

void solve() {
    int n; cin >> n;
    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;
    int ans = 1;
    ordered_set<int> os;
    for (int i = 0; i < n; i++) {
        int cnt = os.order_of_key(b[i]);
        ans = (ans + fact[n - i - 1] * (b[i] - cnt) % MOD) % MOD;
        os.insert(b[i]);
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    precompute(MAX_N);
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

• 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