Submission #3417872


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 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 main()
{
  cin>>N;
  jo[0]=jo[1]=1LL;
  rep1(i,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;
      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 0
Code Size 1609 Byte
Status WA
Exec Time 132 ms
Memory 8816 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 2
AC × 4
WA × 10
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 75 ms 5492 KB
001.txt WA 27 ms 3576 KB
002.txt WA 38 ms 4088 KB
003.txt WA 42 ms 4468 KB
004.txt WA 113 ms 7152 KB
005.txt WA 132 ms 7536 KB
006.txt WA 129 ms 7536 KB
007.txt WA 126 ms 7536 KB
008.txt WA 126 ms 7536 KB
009.txt WA 127 ms 7536 KB
010.txt AC 123 ms 5876 KB
011.txt AC 127 ms 8816 KB
example0.txt AC 2 ms 2304 KB
example1.txt AC 2 ms 2304 KB