Submission #738942

#	Time	Username	Problem	Language	Result	Execution time	Memory
738942		rainboy	W (RMI18_w)	C11	100 / 100	181 ms	6980 KiB

w

#include <stdio.h>
#include <string.h>

#define N	300000
#define MD	1000000007

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

void sort(int *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, a = aa[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[j] == a)
				j++;
			else if (aa[j] < a) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
			}
		sort(aa, l, i);
		l = k;
	}
}

int vv[N + 5], ff[N + 5], gg[N + 5];

void init() {
	int i;

	ff[0] = gg[0] = 1;
	for (i = 1; i <= N + 4; i++) {
		vv[i] = i == 1 ? 1 : (long long) vv[i - MD % i] * (MD / i + 1) % MD;
		ff[i] = (long long) ff[i - 1] * i % MD;
		gg[i] = (long long) gg[i - 1] * vv[i] % MD;
	}
}

int choose(int n, int k) {
	return (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}

int dist(int n, int k) {
	return n < 0 ? 0 : (k == 0 ? (n == 0 ? 1 : 0) : choose(n + k - 1, k - 1));
}

int main() {
	static int aa[N], dp[3][2][2], dq[3][2][2];
	int n, i, j, k, s, s_, l, l1, l_, r, r1, r_;

	init();
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	sort(aa, 0, n);
	for (i = 0; i < n; i = j) {
		j = i + 1;
		while (j < n && aa[j] == aa[i])
			j++;
		k = j - i;
		memset(dq, 0, sizeof dq);
		if (i == 0)
			dq[0][0][0] = 2, dq[1][0][0] = k - 1;
		else
			for (s = 0; s < 3; s++)
				for (l = 0; l < 2; l++)
					for (r = 0; r < 2; r++) {
						int x = dp[s][l][r];

						if (x == 0)
							continue;
						if (s == 0) {
							s_ = 0;
							for (l1 = 0; l1 < 2; l1++) {
								l_ = l | l1, r_ = r;
								dq[s_][l_][r_] = (dq[s_][l_][r_] + (long long) x * dist(k - (l1 == 0 ? 0 : 1), l1 == 0 ? 1 : 2)) % MD;
							}
							s_ = 1;
							for (l1 = 0; l1 < 2; l1++) {
								l_ = l | l1, r_ = r;
								dq[s_][l_][r_] = (dq[s_][l_][r_] + (long long) x * dist(k - 1 - (l1 == 0 ? 0 : 1), l1 == 0 ? 2 : 3)) % MD;
							}
						} else if (s == 1) {
							s_ = 1;
							for (l1 = 0; l1 < 2; l1++)
								for (r1 = 0; r1 < 2; r1++) {
									l_ = l | l1, r_ = r | r1;
									dq[s_][l_][r_] = (dq[s_][l_][r_] + (long long) x * dist(k - (l1 == 0 ? 0 : 1) - (r1 == 0 ? 0 : 1), (l1 == 0 ? 0 : 1) + (r1 == 0 ? 0 : 1) + 2)) % MD;
								}
							s_ = 2;
							for (l1 = 0; l1 < 2; l1++)
								for (r1 = 0; r1 < 2; r1++) {
									l_ = l | l1, r_ = r | r1;
									dq[s_][l_][r_] = (dq[s_][l_][r_] + (long long) x * dist(k - 1 - (l1 == 0 ? 0 : 1) - (r1 == 0 ? 0 : 1), (l1 == 0 ? 0 : 1) + (r1 == 0 ? 0 : 1) + 1)) % MD;
								}
						} else {
							s_ = 2;
							for (l1 = 0; l1 < 2; l1++)
								for (r1 = 0; r1 < 2; r1++) {
									l_ = l | l1, r_ = r | r1;
									dq[s_][l_][r_] = (dq[s_][l_][r_] + (long long) x * dist(k - (l1 == 0 ? 0 : 1) - (r1 == 0 ? 0 : 1), (l1 == 0 ? 0 : 1) + (r1 == 0 ? 0 : 1))) % MD;
								}
						}
					}
		memcpy(dp, dq, sizeof dq);
	}
	printf("%d\n", dp[2][1][1]);
	return 0;
}

Compilation message (stderr)

w.c: In function 'main':
w.c:58:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
w.c:60:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50