Submission #337348

#	Time	Username	Problem	Language	Result	Execution time	Memory
337348		quocnguyen1012	Cryptography (NOI20_crypto)	C++14	100 / 100	159 ms	8164 KiB

Crypto

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxn = 3e5 + 5, mod = 1e9 + 7;

struct BIT {
  int bit[maxn];
  void upd(int i, int v) {
    for (; i < maxn; i += i & -i)
      bit[i] += v;
  }
  int query(int i) {
    int ret = 0;
    for (; i; i -= i & -i) {
      ret += bit[i];
    }
    return ret;
  }
}ft;

int N, a[maxn], fact[maxn];
vector<int> val;

signed main(void) {
  ios_base::sync_with_stdio(0);
	cin.tie(0);
#ifdef LOCAL
	freopen("A.INP", "r", stdin);
	freopen("A.OUT", "w", stdout);
#endif // LOCAL
  fact[0] = 1;
  for (int i = 1; i < maxn; ++i)
    fact[i] = 1ll * fact[i - 1] * i % mod;
  cin >> N;
  for (int i = 1; i <= N; ++i) {
    cin >> a[i];
    val.push_back(a[i]);
  }
  sort(val.begin(), val.end());
  val.erase(unique(val.begin(), val.end()), val.end());
  assert(val.size() == N);
  for (int i = 1; i <= N; ++i) {
    a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;
  }
  int ret = 0;
  for (int i = 1; i <= N; ++i) {
    int val = ft.query(a[i] - 1);
    (ret += 1ll * (a[i] - val - 1) * fact[N - i] % mod) %= mod;
    ft.upd(a[i], 1);
    //cerr << 1ll * (a[i] - val - 1) * fact[N - i] << ' ';
  }
  cout << (ret + 1) % mod;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from Crypto.cpp:1:
Crypto.cpp: In function 'int main()':
Crypto.cpp:43:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |   assert(val.size() == N);
      |          ~~~~~~~~~~~^~~~

• 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