Submission #3419800
Source Code Expand
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<set>
#include<map>
#include<queue>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);++i)
#define rrep(i,n) for(int (i)=(n)-1;(i)>=0;--i)
#define rep1(i,n) for(int (i)=1;(i)<=(n);++i)
#define rrep1(i,n) for(int (i)=(n);(i)>=1;--i)
#define pb push_back
#define fr first
#define sc second
typedef int ss;
#define int long long
typedef long long ll;
typedef pair<int,int> P;
typedef pair<long long,long long> LP;
typedef double db;
using namespace std;
ll N;
ll A[100000];
ll B[100000];
vector<ll> xs;
ll w[200000];
vector<ll> F;
ll mod = 1e+9 + 7;
ll jo[200001];
int extgcd(int a,int b,int& x,int& y){
int d=a;
if(b != 0){
d = extgcd( b , a%b, y, x);
y -= (a/b)*x;
} else{
x=1; y=0;
}
return d;
}
int mod_inverse(int a,int m){
int x,y;
extgcd(a,m,x,y);
return (m+x%m) %m;
}
ll comb(ll n,ll r){
return (((jo[n]*mod_inverse(jo[r],mod)) %mod) *mod_inverse(jo[n-r],mod))%mod;
}
ss main()
{
cin>>N;
jo[0]=jo[1]=1LL;
rep1(i,2*N){
jo[i]= (jo[i-1]*i) %mod;
}
rep(i,N){
cin>>A[i];
xs.pb(A[i]);
}
rep(i,N){
cin>>B[i];
xs.pb(B[i]);
}
sort(xs.begin(),xs.end());
xs.erase( unique(xs.begin(),xs.end()) , xs.end() );
rep(i,N){
A[i] = lower_bound(xs.begin(),xs.end(),A[i]) - xs.begin();
B[i] = lower_bound(xs.begin(),xs.end(),B[i]) - xs.begin();
w[A[i]]=0;
w[B[i]]=1;
}
ll cnt;
for(int i = 0; i< 2*N ;i++){
cnt = 1LL;
while(i + 1 < 2*N && w[i] == w[i+1] ){
i++;
cnt++;
}
F.pb(cnt);
}
ll ans = 1LL;
rep(i,F.size()-1){
if( F[i] <= F[i+1] ){
ans = (ans * jo[F[i]])%mod;
F[i+1]-=F[i];
}
else{
ans = (((ans * jo[F[i+1]])%mod)*comb(F[i],F[i+1]))%mod;
F[i+2] += (F[i]-F[i+1]);
F[i] = F[i+1] = 0;
}
}
cout<<ans<<endl;
}
Submission Info
Submission Time |
|
Task |
A - 1D Matching |
User |
miyajiro |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
2043 Byte |
Status |
AC |
Exec Time |
150 ms |
Memory |
9584 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 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 |
AC |
90 ms |
6004 KB |
001.txt |
AC |
32 ms |
3704 KB |
002.txt |
AC |
45 ms |
4344 KB |
003.txt |
AC |
50 ms |
4724 KB |
004.txt |
AC |
133 ms |
7792 KB |
005.txt |
AC |
149 ms |
8304 KB |
006.txt |
AC |
150 ms |
8304 KB |
007.txt |
AC |
149 ms |
8304 KB |
008.txt |
AC |
150 ms |
8304 KB |
009.txt |
AC |
150 ms |
8304 KB |
010.txt |
AC |
124 ms |
6644 KB |
011.txt |
AC |
129 ms |
9584 KB |
example0.txt |
AC |
2 ms |
2304 KB |
example1.txt |
AC |
2 ms |
2304 KB |