結果
問題 | No.2615 ペアの作り方 |
ユーザー |
|
提出日時 | 2024-01-26 21:35:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 1,405 bytes |
コンパイル時間 | 1,075 ms |
コンパイル使用メモリ | 101,836 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-28 07:45:29 |
合計ジャッジ時間 | 2,549 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>using namespace std;using ll = long long;void solve (int N, vector<int> &X, vector<int> &Y) {// 全部異なる要素とのことなので、XとYの小さい方からN個の和になればいいわけですな// それなら要素が採用されるならmin(X[i], Y[P[i]])のバトルに勝てる必要があるわけで、小さい方から貪欲にとってるわけだからほかの採用メンバーにぶつからない限り必勝のはず// -> ほかの採用メンバーにぶつからないような割り当てならOKconst ll MOD = 998244353;vector<pair<int, char>> Z(2*N);for (int i = 0; i < N; i++) Z[i] = make_pair(X[i], 'X');for (int i = 0; i < N; i++) Z[N+i] = make_pair(Y[i], 'Y');sort(Z.begin(), Z.end(), [](pair<int, char> &a, pair<int, char> &b) { return a.first < b.first; });int k = 0;for (int i = 0; i < N; i++) {if (Z[i].second == 'X') k++;}// 解はk!(N-k)!ll ans = 1;for (int i = 1; i <= k; i++) {ans *= i;ans %= MOD;}for (int i = 1; i <= N-k; i++) {ans *= i;ans %= MOD;}cout << ans << "\n";}int main () {int N; cin >> N;vector<int> X(N), Y(N);for (int i = 0; i < N; i++) cin >> X[i];for (int i = 0; i < N; i++) cin >> Y[i];solve(N, X, Y);}