Submission #1837467


Source Code Expand

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

const int M = 1000000007;

//x^n mod M
typedef long long ull;
ull power(ull x, ull n, ull M){
	ull res = 1;
	if(n > 0){
		res = power(x, n / 2, M);
		if(n % 2 == 0) res = (res * res) % M;
		else res = (((res * res) % M) * x ) %M;
	}
	return res;
}

int main(){
	int n;
	cin >> n;

	vector<pair<int, bool>> p(n * 2); //1 : PC, 0 : power supply
	rep(i,n){
		int a;
		cin >> a;
		p[i] = make_pair(a, true);
	}
	rep(i,n){
		int b;
		cin >> b;
		p[i + n] = make_pair(b, false);
	}


	sort(all(p));

	int cnt = 0, cur = -1;
	vector<int> v;
	rep(i,n * 2){
		cnt += p[i].second ? 1 : -1;
		//show(cnt)
		if(cnt == 0){
			v.emplace_back((i - cur) / 2);
			cur = i;
		}
	}

	//for(auto i : p){ cout << i.second << ' ' ; } cout << endl;

	long long ans = 1;
	for(auto i : v){
		//show(i)
		vector<long long> c(i + 1);
		rep(j,i + 1){
			if(j == 0) c[j] = 1;
			else{
				c[j] = c[j - 1] * (i - (j - 1)) % M * power(j, M - 2, M) % M;
			}
		}

		long long m = 1;
		rep(j,i){
			m *= c[j];
			m %= M;
		}
		(ans *= m) %= M;
	}
	cout << ans << endl;
}

Submission Info

Submission Time
Task A - 1D Matching
User noy72
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1370 Byte
Status WA
Exec Time 158 ms
Memory 2560 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 2
AC × 3
WA × 11
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 95 ms 1536 KB
001.txt WA 36 ms 768 KB
002.txt WA 49 ms 768 KB
003.txt WA 54 ms 896 KB
004.txt WA 141 ms 2176 KB
005.txt WA 157 ms 2048 KB
006.txt WA 157 ms 2176 KB
007.txt WA 157 ms 2048 KB
008.txt WA 158 ms 2432 KB
009.txt WA 157 ms 2048 KB
010.txt WA 157 ms 2560 KB
011.txt AC 155 ms 2428 KB
example0.txt AC 1 ms 256 KB
example1.txt AC 1 ms 256 KB