Submission #332993

#	Time	Username	Problem	Language	Result	Execution time	Memory
332993		Cantfindme	Cryptography (NOI20_crypto)	C++17	100 / 100	143 ms	12780 KiB

Crypto

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
const int maxn = 300010;
const int mod = 1e9+7;

int n;

int ft[maxn];
int fac[maxn];

vector <int> disc(vector <int> V) {
	vector <int> dis = V;
	sort(dis.begin(),dis.end());
	dis.resize(unique(dis.begin(),dis.end()) - dis.begin());
	for (int i =0;i<(int)V.size();i++) {
		V[i] = lower_bound(dis.begin(),dis.end(),V[i]) - dis.begin() + 1;
	}
	return V;
}

int ls(int x) {
	return x & (-x);
}

void up(int x, int v) {
	for (;x <= n; x += ls(x)) ft[x] += v;
}

int query(int x) {
	int res = 0;
	for (; x; x -= ls(x)) res += ft[x];
	return res;
}

void add(int &a, int b) {
	a += b;
	a %= mod;
}

int32_t main() {
	FAST
	cin >> n;
	vector <int> v(n);
	fac[0] = 1;
	for (int i =1;i<=n;i++) {
		fac[i] = (fac[i-1] * i) % mod;
	}
	
	for (int i =0;i<n;i++) {
		cin >> v[i];
	}
	v = disc(v);
	
	//cout << "HELLO\n";
	//for (int i =1;i<=n;i++) {
		//cout << v[i-1] << "\n";
	//}
	
	int ans = 0;
	for (int i =1;i<=n;i++) {
		int x = v[i-1];
		int taken = query(x-1);
		if (x-taken-1 > 0) {
			//cout << x << " " << taken << " " << fac[n-i] << "\n"; 
			int res = ((x - taken - 1) * fac[n-i] % mod)%mod;
			add(ans,res%mod);
		}
		up(x,1);
	}
	cout << (ans+1)%mod;
	
}

• 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