# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1124203 | seoul_korea | Cryptography (NOI20_crypto) | C++17 | 120 ms | 10008 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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |