Submission #697513

#	Time	Username	Problem	Language	Result	Execution time	Memory
697513		borisAngelov	Cryptography (NOI20_crypto)	C++17	100 / 100	168 ms	17784 KiB

Crypto

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int maxn = 300005;
const long long mod = 1000000007;

int n;

int a[maxn];

void read()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
}

void compress()
{
    vector<int> to_compress;

    for (int i = 1; i <= n; ++i)
    {
        to_compress.push_back(a[i]);
    }

    sort(to_compress.begin(), to_compress.end());

    unordered_map<int, int> compressed_values;

    for (int i = 0; i < to_compress.size(); ++i)
    {
        compressed_values[to_compress[i]] = i + 1;
    }

    for (int i = 1; i <= n; ++i)
    {
        a[i] = compressed_values[a[i]];
    }
}

int fenwick[maxn];

void update(int pos, int val)
{
    while (pos <= n)
    {
        fenwick[pos] += val;
        pos += (pos & (-pos));
    }
}

int query(int pos)
{
    int result = 0;

    while (pos >= 1)
    {
        result += fenwick[pos];
        pos -= (pos & (-pos));
    }

    return result;
}

long long factoriels[maxn];

void solve()
{
    factoriels[1] = 1;

    for (int i = 2; i <= n; ++i)
    {
        factoriels[i] = (factoriels[i - 1] * (1LL * i)) % mod;
    }

    for (int i = 1; i <= n; ++i)
    {
        update(a[i], +1);
    }

    long long ans = 0;

    for (int i = 1; i <= n; ++i)
    {
        long long cnt_smaller = query(a[i] - 1);

        ans = (ans + cnt_smaller * factoriels[n - i]) % mod;
        //cout << i << ' ' << a[i] << ' ' << cnt_smaller << ' ' << factoriels[n - i] << endl;

        update(a[i], -1);
    }

    ans = (ans + 1) % mod;

    cout << ans << endl;
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    read();
    compress();
    solve();

    return 0;
}

Compilation message (stderr)

Crypto.cpp: In function 'void compress()':
Crypto.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < to_compress.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~

• 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