Submission #680099

#	Time	Username	Problem	Language	Result	Execution time	Memory
680099		rainboy	Security Gate (JOI18_security_gate)	C11	30 / 100	333 ms	340 KiB

securitygate

#include <stdio.h>

#define N	300
#define K	20

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int solve(char *cc, int n) {
	static int xx[N + 1];
	int i, a, b, l, r;

	xx[0] = 0;
	for (i = 0; i < n; i++)
		xx[i + 1] = xx[i] + (cc[i] == '(' ? 1 : -1);
	if (xx[n] % 2 != 0)
		return 0;
	for (l = 0; l <= n; l++)
		if (xx[l] < 0)
			break;
	l--;
	for (r = n; r >= 0; r--)
		if (xx[r] - xx[n] < 0)
			break;
	r++;
	a = xx[0];
	for (i = 0; i <= l; i++)
		a = max(a, xx[i]);
	b = xx[n];
	for (i = r; i <= n; i++)
		b = max(b, xx[i]);
	if (l == n && r == 0)
		return 1;
	else if (l == n) {
		for (i = n; i >= 0; i--) {
			if ((b - xx[n] / 2) * 2 - xx[i] < 0)
				return 0;
			if (b - xx[i] == xx[n] / 2)
				return 1;
		}
		return 0;
	} else if (r == 0) {
		for (i = 0; i <= n; i++) {
			if (a * 2 - xx[i] < 0)
				return 0;
			if (xx[i] - a == xx[n] / 2)
				return 1;
		}
		return 0;
	} else {
		for (i = l; i <= r; i++)
			if (min(a, b - xx[n] / 2) * 2 - xx[i] < 0)
				return 0;
		return 1;
	}
}

int main() {
	static char cc[N + 1];
	static int ii[K];
	int n, k, h, i, b, ans;

	scanf("%d%s", &n, cc);
	k = 0;
	for (i = 0; i < n; i++)
		if (cc[i] == 'x')
			ii[k++] = i;
	ans = 0;
	for (b = 0; b < 1 << k; b++) {
		for (h = 0; h < k; h++)
			cc[ii[h]] = (b & 1 << h) == 0 ? '(' : ')';
		if (solve(cc, n))
			ans++;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

securitygate.c: In function 'main':
securitygate.c:63:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d%s", &n, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 43
• Subtask 5: 0 / 27