Submission #2012647


Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <nmmintrin.h>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 10000000
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to, weight;

	bool operator < (const Edge& obj) const {
		return weight < obj.weight;
	}
	bool operator > (const Edge& obj) const {
		return weight > obj.weight;
	}
};

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) { //xの入って る集合と yの入ってる集合を併合
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { //xとyが同じ集合に入っているかどうかを判定
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	bool isroot(int x) {
		return data[x] < 0;
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int arr[100001];
void Eratosthenes(int N) {//Nまでの素数表
	for (int i = 0; i < N; i++) {
		arr[i] = 1;
	}
	for (int i = 2; i < sqrt(N); i++) {
		if (arr[i]) {
			for (int j = i * 2; j <= N; j += i) {
				arr[j] = 0;
			}
		}
	}
}
typedef pair<ll, ll> pll;
mt19937 ran;

int Has[4] = { (int)(ran() / 100),(int)(ran() / 100),(int)(ran() / 100),(int)(ran() / 100) };

struct RollingHash {
	const pll bai = { 181243 ,2251 };
	vector<pll> hash;
	vector<pll> base;
	int len;
	RollingHash(string str) : hash(str.length() + 1), base(str.length() + 1) {
		len = str.length();
		base[0].first = 1;
		base[0].second = 1;

		REP(i, len) {
			int num = str[i] == 'A' ? 0 : str[i] == 'T' ? 1 : str[i] == 'G' ? 2 : 3;
			(hash[i + 1].first = hash[i].first * bai.first + Has[num]) %= MODU;
			(hash[i + 1].second = hash[i].second * bai.second + Has[num]) %= 129402307;
			(base[i + 1].first = base[i].first * bai.first) %= MODU;
			(base[i + 1].second = base[i].second * bai.second) %= 129402307;
		}
	}

	pll Gethash(int l, int r) {
		return { (hash[r].first - (hash[l].first * base[r - l].first) % MODU + MODU) % MODU, (hash[r].second - (hash[l].second * base[r - l].second) % 129402307 + 129402307) % 129402307 };
	}

};

struct BIT {
#define SZ(a) (a & (-a))
#define LEFT(a) (a - SZ(a))
#define UP(a) (a + SZ(a))

	vector<int> x;

	BIT(int n) : x(n + 1) {}

	int sum(int r) {
		r++;
		int ret = 0;
		for (int i = r; 0 < i; i = LEFT(i)) {
			ret += x[i];
		}
		return ret;
	}

	void add(int r, int v) {
		r++;
		for (int i = r; i < x.size(); i = UP(i)) {
			x[i] += v;
		}
	}
};

ll fc[100001];

int factorial(ll a, ll lm) {
	if (fc[a]) return fc[a];
	if (a == lm) return a;
	return (fc[a] = factorial(a-1, lm) * a) %= MODU;
}

int main()
{
	int n;
	cin >> n;
	vector<pii> len(n * 2);
	REP(i, n) {
		scanf("%d", &len[i].first);
		len[i].second = 0;
	}
	REP(i, n) {
		scanf("%d", &len[i + n].first);
		len[i + n].second = 1;
	}
	sort(ALL(len));

	int cou[2] = {};
	int befc = -1;
	ll ans = 1;
	REP(i, n * 2) {
		cou[len[i].second]++;
		if (i < n * 2 - 1 && (cou[0] == cou[1] || (len[i].second != len[i+1].second && cou[0] && cou[1]))) {
			int mx = max(cou[0], cou[1]), mn = min(cou[0], cou[1]);
			(ans *= factorial(mx, mx-mn + 1)) %= MODU;
			int g = min(cou[0], cou[1]);
			cou[0] -= g;
			cou[1] -= g;
			befc = i;
		}
	}
	int mx = max(cou[0], cou[1]), mn = min(cou[0], cou[1]);
	(ans *= factorial(mx, mx - mn + 1)) %= MODU;
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task A - 1D Matching
User Gear
Language C++14 (Clang 3.8.0)
Score 0
Code Size 4900 Byte
Status WA
Exec Time 45 ms
Memory 4224 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 27 ms 1280 KB
001.txt WA 10 ms 640 KB
002.txt WA 14 ms 768 KB
003.txt WA 15 ms 768 KB
004.txt WA 39 ms 1664 KB
005.txt WA 44 ms 1792 KB
006.txt WA 44 ms 1792 KB
007.txt WA 44 ms 1792 KB
008.txt WA 44 ms 1792 KB
009.txt WA 44 ms 1792 KB
010.txt WA 45 ms 4224 KB
011.txt AC 44 ms 1792 KB
example0.txt AC 1 ms 256 KB
example1.txt AC 1 ms 256 KB