Submission #1306992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306992		abyfu	Cryptography (NOI20_crypto)	C++20	35 / 100	247 ms	33892 KiB

Crypto

//OwO
//#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define namein "input.txt"
#define nameout "output.txt"
#define pque priority_queue
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pb push_back
#define m_pi acos(-1)
using namespace std;
const ll inf = 4e18;    
const int linf = 1.5e9;

void file(){
    if (fopen(namein, "r")){
        freopen(namein, "r", stdin);
        freopen(nameout, "w", stdout);
    }   
}


const ll mod = 1e9 + 7;
const int N = 3e5 + 5, M = 5e1 + 5;
map<int, int> v;
set<int> x;
int a[N];    
int t[4*N];

int get(int i, int l, int r, int u, int v){
    if (r < u || v < l) return 0;
    else if (u <= l && r <= v) return t[i];
    int m = (l + r)/2;
    return get(2*i, l, m, u, v) + get(2*i + 1, m + 1, r, u, v);
}

void update(int i, int l, int r, int u, int v){
    if (r < u || v < l) return;
    else if (u <= l && r <= v){
        t[i]++;
        return;
    }
    int m = (l + r)/2;
    update(2*i, l, m, u, v); update(2*i + 1, m + 1, r, u, v);
    t[i] = t[2*i] + t[2*i + 1];
}

void run(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        x.insert(a[i]);
    }
    int c = 1;
    for (auto i : x){
        v[i] = c++;
    }
    for (int i = 1; i <= n; i++) a[i] = v[a[i]];
    ll rs = 0, fc = 1;
    update(1, 1, n, a[n], a[n]);
    for (int i = n - 1; i >= 1; i--){
        rs = (rs + fc*(a[i] == 1 ? 0 : get(1, 1, n, 1, a[i] - 1)) % mod) % mod;
        update(1, 1, n, a[i], a[i]);
        fc = (fc*(n + 1 - i)) % mod;
    }
    cout << rs + 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);
    file();
    run();
}

Compilation message (stderr)

Crypto.cpp: In function 'void file()':
Crypto.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(namein, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Crypto.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(nameout, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 9 / 9
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 21
• Subtask 6: 0 / 13
• Subtask 7: 0 / 19
• Subtask 8: 0 / 12