Submission #1003139

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>

using namespace std;

#define TASKNAME ""

void solve(int test_number);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(ios::fixed);
    cout.precision(9);
    cerr.setf(ios::fixed);
    cerr.precision(3);
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
#endif
    int n = 1;
    for (int i = 0; i < n; i++) {
        solve(i);
    }
}

const int MAX_N = 100005;
const int MOD = 1000000007;


int n, a[MAX_N], b[MAX_N], fact[MAX_N];

void solve(int test_number) {
    cin >> n;
    /*
    srand(time(0));
    n = 7;
    bool used[100] = {false};
    int val[100], sz = 0;
    for (int i = 0; i < n; i++) {
        int x;
        do {
            x = rand() % 100;
        } while (used[x]);
        used[x] = true;
        a[i] = x;
        val[sz++] = x;
    }
    for (int i = 0; i < n; i++) {
        int x;
        do {
            x = rand() % 100;
        } while (used[x]);
        used[x] = true;
        b[i] = x;
        val[sz++] = x;
    }
    sort(val, val + sz);
    sz = unique(val, val + sz) - val;
    */
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    sort(a, a + n);
    sort(b, b + n);
    /*
    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(val, val + sz, a[i]) - val;
        cout << a[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        b[i] = lower_bound(val, val + sz, b[i]) - val;
        cout << b[i] << " ";
    }
    cout << endl;
    int min_ans = 0;
    for (int i = 0; i < n; i++) {
        min_ans += abs(a[i] - b[i]);
    }
    cout << "MIN ANS: " << min_ans << endl;
    int perm[12];
    for (int i = 0; i < n; i++) {
        perm[i] = i;
    }
    int brute_ans = 0;
    do {
        int cur_ans = 0;
        for (int i = 0; i < n; i++) {
            cur_ans += abs(a[i] - b[perm[i]]);
        }
        if (cur_ans == min_ans) {
            for (int j = 0; j < n; j++) {
                cout << perm[j] << " ";
            }
            cout << endl;
            brute_ans++;
        }
    } while (next_permutation(perm, perm + n));
    cout << "BRUTE ANS : " << brute_ans << endl;
    */
    int ans = 1;
    int var = 0;
    int i = 0, j = 0;
    while (i < n || j < n) {
        if (var == 0 && (i == n || a[i] < b[j])) {
            swap(a, b);
            swap(i, j);
        }
        while (j < n && b[j] < a[i]) {
            var++;
            j++;
        }
        i++;
        ans = ans * max(1, var) % MOD;
        var--;
    }
    cout << ans << endl;
}

Submission Info

Judge Result