Submission #3883366
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define endl "\n"
#define show(x) cerr << #x << " " << x << endl
typedef long long ll;
typedef unsigned long long ull;
constexpr const int INT_INF=0x3f3f3f3f; // 1061109567
constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f; // 4557430888798830399
template <typename T> bool chmin(T &a, T b) {
if (a > b) {a = b;return true;}return false;
}
template <typename T> bool chmax(T &a, T b) {
if (a < b) {a = b;return true;}return false;
}
// INT
#define GCD(a, b) __gcd(a, b)
template <typename T> T LCM(T a, T b) {return a / GCD(a, b) * b;}
template <typename T> T EXTGCD(T a, T b, T& x, T& y) {
T d = a;
if (b != 0) {d=EXTGCD(b,a%b,y,x);y-=(a/b)*x;}
else x=1,y=0;
return d;
}
template <typename T> bool is_prime(T a) {
for(int i=2;i*i<=a;i++)if(a%i==0)return 1;
return 0;
}
// MOD
const ll MOD = 1000000000 + 7;
#define add(a, b) ((a % MOD) + (b % MOD)) % MOD
#define mul(a, b) ((a % MOD) * (b % MOD)) % MOD
#define sub(a, b) ((a % MOD) + MOD - (b % MOD)) % MOD
template <typename T> T mod_inverse(T a, T mod, bool prime){ // if mod is prime, "prime" is true.
if(prime){
T tmp=mod-2,now=a,res=1;while(tmp){if(tmp&1)res=mul(res,now);now=mul(now,now);tmp>>=1;}
return res;
}else{T x,y;EXTGCD(a,mod,x,y);return (mod+x%mod)%mod;}
}
#define divide(a, b) ((a % MOD) * (mod_inverse(b, MOD, true))) % MOD
//LLの数値をつかう時は最後にLをつける癖をつけよう
//
// ┓ ┏
// *┗┓ ┏┛
// ┫ ┣ *
// ┏┳┻━┻┳┓
// ┗┫ ┣┛
// * ┣ ━┃ * Merry Christmas!!
// ┏┛ 〃┃
// ┃● ┣━┳┓
// ┗┻┳━━┛ ┣┛
// * ┃┏┓┣┓┃
//WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
int n;
ll a[100001];
ll b[100001];
vector <pair <ll, ll> > v;
ll func(ll now) {
ll res = 1L;
for (ll i = now; i >= 2; i--) {
res = mul(res, i);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(10);
cout << fixed;
#ifdef LOCAL_DEFINE
FILE *stream1;
//FILE *stream2;
stream1 = freopen("/Users/aim_cpo/CLionProjects/competitive/in.txt", "r", stdin);
//stream2 = freopen("out.txt", "w", stdout);
if (stream1 == nullptr) return 0;
//if (stream2 == NULL) return 0;
#endif
cin >> n;
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++) {
if (a[i] > b[i]) swap(a[i], b[i]);
v.push_back(mp(a[i], b[i]));
}
ll l = v[0].fi, r = v[0].se;
int now = 1;
ll ans = 1L;
for (int i = 1; i < n; i++) {
ll nowl = v[i].fi, nowr = v[i].se;
if (r < nowl || l > nowr) {
ans = mul(ans, func(now));
now = 1;
l = v[i].fi, r = v[i].se;
continue;
}
chmin(l, nowl);
chmax(r, nowr);
now++;
}
ans = mul(ans, func(now));
cout << ans << endl;
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
#endif
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 1D Matching |
User |
aim_cpo |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3548 Byte |
Status |
WA |
Exec Time |
37 ms |
Memory |
4084 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0.txt, example1.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, example0.txt, example1.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
WA |
22 ms |
2424 KB |
001.txt |
WA |
8 ms |
1276 KB |
002.txt |
WA |
12 ms |
1404 KB |
003.txt |
WA |
13 ms |
1912 KB |
004.txt |
WA |
32 ms |
3828 KB |
005.txt |
WA |
36 ms |
3956 KB |
006.txt |
WA |
36 ms |
3956 KB |
007.txt |
WA |
36 ms |
3956 KB |
008.txt |
WA |
36 ms |
3956 KB |
009.txt |
WA |
36 ms |
3956 KB |
010.txt |
AC |
36 ms |
3956 KB |
011.txt |
AC |
37 ms |
4084 KB |
example0.txt |
AC |
1 ms |
256 KB |
example1.txt |
AC |
1 ms |
256 KB |