Submission #1011975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011975		kaopj	Cryptography (NOI20_crypto)	C++17	88 / 100	1002 ms	33692 KiB

Crypto

#include <iostream>
#include <vector>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define orderedset tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define lgm cin.tie(0)->sync_with_stdio(0);
const int mod = 1e9+7;
using namespace std;
signed main() {
    lgm;
    orderedset s;
    int n;
    cin >> n;
    vector<pair<int,int>> o(n);
    vector<int> num(n);
    for (int i=0;i<n;i++) {
        cin >> num[i];
        o[i]={num[i],i};
    }
    sort(o.begin(),o.end());
    int ans=0;
    for (int i=0;i<n;i++) {
        num[o[i].second]=i;
    }
    vector<int> lesscnt(n);
    int f[n+1];
    f[0]=1;
    f[1]=1;
    for (int i=2;i<=n;i++) {
        f[i]=i*f[i-1]%mod;
    }
    for (int i=n-1;i>=0;i--) {
        int l=0,r=n-1-i,m;
        while (l<r) {
            m=(l+r)>>1;
            if (*s.find_by_order(m) >= num[i]) {
                r=m;
            } else {
                l=m+1;
            }
        }
        lesscnt[i]=l;
        s.insert(num[i]);
    }
    for (int i=0;i<n;i++) {
        ans=(ans+f[n-i-1]*lesscnt[i]%mod)%mod;
    }
    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: 0 / 12