Submission #1265483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265483		phtung	Cryptography (NOI20_crypto)	C++20	100 / 100	155 ms	9904 KiB

Crypto

#include <bits/stdc++.h>

using namespace std;

#define name "IO"
#define int long long 

const int mod = 1e9 + 7; 
const int inf = 1e18 + 7; 
const int maxn = 3e5 + 5;
int n, p[maxn], fac[maxn]; 
vector<int> val; 

struct Fenw
{
    vector<int> tree;

    Fenw(int n)
    {
        tree.resize(n + 5, 0); 
    }

    void update(int i, int x)
    {
        for(i; i <= n; i += i &-i) tree[i] += x; 
    }

    int get(int i)
    {
        int res = 0; 
        for(i; i > 0; i -= i & -i) res += tree[i];
        return res; 
    }

};

void solve()
{
    cin >> n;

    fac[0] = 1; 
    for(int i = 1; i <= n; i++) 
    {
        cin >> p[i];
        val.push_back(p[i]);
        fac[i] = (fac[i - 1] * i) % mod; 
    } 

    sort(val.begin(), val.end()); 
    val.erase(unique(val.begin(), val.end()), val.end()); 
    Fenw bit(n); 

    auto get = [&](int x) 
    {
        int pos = lower_bound(val.begin(), val.end(), x) - val.begin() + 1; 
        return pos; 
    };

    for(int i = 1; i <= n; i++)
    {
        bit.update(get(p[i]), 1); 
    }

    int ans = 1; 
    for(int i = 1; i <= n; i++)
    {
        int pos = get(p[i]); 
        bit.update(pos, -1); 
        int cnt = bit.get(pos);
        ans = (ans + cnt * fac[n - i]) % mod; 
    }

    cout << ans << "\n";





    
}

signed main()
{
    if (fopen (name".INP", "r"))
    {
        freopen (name".INP", "r", stdin);
        freopen (name".OUT", "w", stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    clock_t start = clock(); 

    int t = 1;

    while(t--) solve(); 

    std::cerr << "Time: " << clock() - start << "ms\n";

    return 0; 

}

Compilation message (stderr)

Crypto.cpp: In function 'int main()':
Crypto.cpp:86:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen (name".INP", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Crypto.cpp:87:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen (name".OUT", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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