Submission #1060287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060287		rainboy	Sprinklers (CEOI24_sprinklers)	C11	9 / 100	56 ms	4004 KiB

Main

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

#define N	100000
#define M	100000
#define X	1000000001

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

char cc[N + 1]; int xx[N + 2], yy[M], n, m;

int solve(int d) {
	static int dp[N + 2], pp[N + 2];
	int i, i_, i1, j, x, y;

	memset(dp, -1, (n + 2) * sizeof *dp);
	dp[0] = 0;
	for (i = 0, i_ = 0, j = 0; i <= n; i++) {
		if (dp[i] == -1)
			return 0;
		while (j < m && yy[j] < xx[i])
			j++;
		x = max(xx[i], xx[dp[i]] + d), y = -1;
		while (j < m && yy[j] < xx[i + 1]) {
			if (yy[j] > x) {
				y = yy[j];
				break;
			}
			j++;
		}
		if (y == -1)
			dp[i + 1] = i + 1, pp[i + 1] = i;
		else {
			i_ = max(i_, i + 1);
			while (i_ <= n + 1 && y >= xx[i_] - d) {
				i1 = i_ == i + 1 ? dp[i] : i_ - 1;
				if (dp[i_] < i1)
					dp[i_] = i1, pp[i_] = i;
				i_++;
			}
		}
	}
	if (dp[n + 1] == -1)
		return 0;
	i = n;
	while (i > 0)
		if (pp[i] == i - 1)
			cc[i - 1] = dp[i] == i ? 'R' : 'L', i--;
		else {
			cc[--i] = 'L';
			while (i > pp[i])
				cc[--i] = 'R';
		}
	return 1;
}

int main() {
	int m_, i, y, d, lower, upper;

	scanf("%d%d", &n, &m);
	xx[0] = -X - 1, xx[n + 1] = X * 2 + 1;
	for (i = 1; i <= n; i++)
		scanf("%d", &xx[i]);
	m_ = 0, i = 0;
	while (m--) {
		scanf("%d", &y);
		while (xx[i] < y)
			i++;
		if (xx[i] != y)
			yy[m_++] = y;
	}
	m = m_;
	lower = -1, upper = X;
	while (upper - lower > 1) {
		d = (lower + upper) / 2;
		if (solve(d))
			upper = d;
		else
			lower = d;
	}
	if (upper == X) {
		printf("-1\n");
		return 0;
	}
	solve(upper);
	printf("%d\n", upper);
	printf("%s\n", cc);
	return 0;
}

Compilation message (stderr)

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

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47