Submission #733834

#	Time	Username	Problem	Language	Result	Execution time	Memory
733834		vjudge1	Cryptography (NOI20_crypto)	C++17	100 / 100	153 ms	9936 KiB

Crypto

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

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

#define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
    out << c.first << ' ' << c.second;
    return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
    const int sz = v.size();
    for (int i = 0; i < sz; i++) {
        if (i) out << ' ';
        out << v[i];
    }
    return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
    for (T &x : v) in >> x;
    return in;
}

template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

void go() {
	int n;
	cin >> n;
	const int mod = 1e9 + 7;
	vector<int> a(n);
	vector<int> tmp;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		tmp.pb(a[i]);
	}
	vector<int> sum(n + 10, 0);

	auto up = [&](int l, int val) -> void {
		for(; l <= n; l += (l & -l)) {
			sum[l] += val;
		}
	};

	auto get = [&](int l) -> int {
		int ret = 0;
		for(; l; l -= (l & -l)) {
			ret += sum[l];
		}
		return ret;
	};

	sort(all(tmp));
	tmp.erase(unique(all(tmp)), tmp.end());
	for(int i = 0; i < n; i++) {
		a[i] = lower_bound(all(tmp), a[i]) - tmp.begin() + 1;		
		up(i + 1, 1);
	}
	vector<int> f(n + 10);
	f[0] = 1;
	for(int i = 1; i <= n; i++) {
		f[i] = (f[i - 1] * i) % mod;
	}
	int ans = 0;
	for(int i = 0; i < n; i++) {
		ans = (ans + get(a[i] - 1) * f[n - i - 1]) % mod;
		up(a[i], -1);
	}
	cout << (ans + 1) % mod << '\n';
}

signed main() {
    fast;
    int t = 1;
    // cin >> t;
    while(t--) {
        go();
    }
    return 0;
}

• 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