Submission #1124203

#TimeUsernameProblemLanguageResultExecution timeMemory
1124203seoul_koreaCryptography (NOI20_crypto)C++17
100 / 100
120 ms10008 KiB
#include <bits/stdc++.h> using namespace std; #define TASK "NOI20_crypto" #define int long long #define REP(i, n) for(int i = 1; i <= n; i++) #define FOR(i, a, b) for(auto i = a; i <= b; i++) #define FORD(i, a, b) for(auto i = a; i >= b; i--) template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; } template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; } const int N = (int)3e5 + 7, MOD = (int)1e9 + 7; int a[N], fact[N]; int n; void add(int& a, int b) { a += b; if(a >= MOD) a -= MOD; if(a < 0) a += MOD; } struct FenwickTree { vector<int> BIT; FenwickTree(int _sz) { BIT.assign(_sz + 1, 0); } void Ins(int x, int val) { int sz = BIT.size(); for(; x < sz; x += x & -x) BIT[x] += val; } int Get(int x) { int res = 0; for(; x > 0; x -= x & -x) res += BIT[x]; return res; } }; signed main() { cin.tie(0)->ios_base::sync_with_stdio(0); if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin); if(fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); freopen(TASK".OUT", "w", stdout); } cin >> n; FenwickTree tree(n + 10); vector<int> zip; REP(i, n) { cin >> a[i]; zip.push_back(a[i]); } sort(zip.begin(), zip.end()); zip.resize(unique(zip.begin(), zip.end()) - zip.begin()); REP(i, n) { a[i] = lower_bound(zip.begin(), zip.end(), a[i]) - zip.begin() + 1; tree.Ins(a[i], 1); } fact[0] = 1; REP(i, n) fact[i] = fact[i - 1] * i % MOD; int ans = 0; REP(i, n) { int p = tree.Get(a[i]); add(ans, (p - 1) * fact[n - i] % MOD); tree.Ins(a[i], -1); } add(ans, 1); cout << ans << endl; /* * x* **x *x** ***xx */ return 0; }

Compilation message (stderr)

Crypto.cpp: In function 'int main()':
Crypto.cpp:51:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Crypto.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Crypto.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...