oj.uz

Submission #1060306

# Submission time Handle Problem Language Result Execution time Memory
1060306 2024-08-15T12:52:02 Z rainboy Sprinklers (CEOI24_sprinklers) C
0 / 100
 13 ms 860 KB 
#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++) {
		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

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Incorrect 8 ms 600 KB User solution is incorrect
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 10 ms 604 KB Correct
3 Incorrect 3 ms 344 KB User solution is incorrect
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 0 ms 348 KB Correct
4 Incorrect 0 ms 348 KB User solution is incorrect
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Incorrect 13 ms 860 KB User solution is incorrect
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Incorrect 8 ms 600 KB User solution is incorrect
4 Halted 0 ms 0 KB -