Submission #889113

#	Time	Username	Problem	Language	Result	Execution time	Memory
889113		rainboy	World of Tank (innopolis2018_final_E)	C11	100 / 100	296 ms	175532 KiB

E

/* https://codeforces.com/blog/entry/58056 */
#include <stdio.h>
#include <string.h>

#define N	2000001

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

int xx1[N], xx2[N], xx[N], bb[N], n, t;

int dp[N * 2], pp[N * 2];

void update(int u, int v, int x) {
	if (dp[v] < x)
		dp[v] = x, pp[v] = u;
}

int xx_[N], m;
int yy1[N], k;

int trace(int u) {
	int i, x, y;

	if (u == (0 << 1 | 0))
		return t;
	i = u >> 1, y = u & 1;
	x = trace(pp[u]);
	if (pp[u] == (u ^ 1)) {
		xx_[m++] = xx[i];
		x = max(x, xx[i]);
	} else if ((bb[i] & 1 << y) != 0)
		xx1[k] = x, yy1[k] = y + 1, k++, x += t;
	return x;
}

int main() {
	int n1, n2, x_, h, i, i1, i2, u;

	scanf("%d%d%d%d", &x_, &n1, &n2, &t);
	for (i = 0; i < n1; i++)
		scanf("%d", &xx1[i]);
	xx1[n1] = x_ + 1;
	for (i = 0; i < n2; i++)
		scanf("%d", &xx2[i]);
	xx2[n2] = x_ + 1;
	i1 = 0, i2 = 0, n = 0;
	xx[n] = 0, bb[n] = 0, n++;
	while (i1 < n1 || i2 < n2)
		if (xx1[i1] < xx2[i2]) {
			if (xx[n - 1] + 1 < xx1[i1])
				xx[n] = xx[n - 1] + 1, bb[n] = 0, n++;
			xx[n] = xx1[i1], bb[n] = 1, n++;
			i1++;
		} else if (xx1[i1] > xx2[i2]) {
			if (xx[n - 1] + 1 < xx2[i2])
				xx[n] = xx[n - 1] + 1, bb[n] = 0, n++;
			xx[n] = xx2[i2], bb[n] = 2, n++;
			i2++;
		} else {
			if (xx[n - 1] + 1 < xx1[i1])
				xx[n] = xx[n - 1] + 1, bb[n] = 0, n++;
			xx[n] = xx1[i1], bb[n] = 3, n++;
			i1++, i2++;
		}
	memset(dp, -1, n * 2 * sizeof *dp), memset(pp, -1, n * 2 * sizeof *pp), dp[0 << 1 | 0] = 0;
	for (i = 0; i < n; i++) {
		if (dp[i << 1 | 0] != -1 && (bb[i] & 2) == 0)
			update(i << 1 | 0, i << 1 | 1, min(dp[i << 1 | 0], t));
		if (dp[i << 1 | 1] != -1 && (bb[i] & 1) == 0)
			update(i << 1 | 1, i << 1 | 0, min(dp[i << 1 | 1], t));
		if (i + 1 < n) {
			if (dp[i << 1 | 0] != -1) {
				if ((bb[i + 1] & 1) == 0)
					update(i << 1 | 0, i + 1 << 1 | 0, dp[i << 1 | 0] + xx[i + 1] - xx[i]);
				else if (dp[i << 1 | 0] + xx[i + 1] - xx[i] - 1 >= t)
					update(i << 1 | 0, i + 1 << 1 | 0, dp[i << 1 | 0] + xx[i + 1] - xx[i] - t);
			}
			if (dp[i << 1 | 1] != -1) {
				if ((bb[i + 1] & 2) == 0)
					update(i << 1 | 1, i + 1 << 1 | 1, dp[i << 1 | 1] + xx[i + 1] - xx[i]);
				else if (dp[i << 1 | 1] + xx[i + 1] - xx[i] - 1 >= t)
					update(i << 1 | 1, i + 1 << 1 | 1, dp[i << 1 | 1] + xx[i + 1] - xx[i] - t);
			}
		}
	}
	if (dp[n - 1 << 1 | 0] == -1 && dp[n - 1 << 1 | 1] == -1) {
		printf("No\n");
		return 0;
	}
	u = dp[n - 1 << 1 | 0] != -1 ? n - 1 << 1 | 0 : n - 1 << 1 | 1;
	if (pp[u] == (u ^ 1))
		u ^= 1;
	trace(u);
	printf("Yes\n");
	printf("%d\n", m);
	for (h = 0; h < m; h++)
		printf("%d ", xx_[h]);
	printf("\n");
	printf("%d\n", k);
	for (h = 0; h < k; h++)
		printf("%d %d\n", xx1[h], yy1[h]);
	return 0;
}

Compilation message (stderr)

E.c: In function 'main':
E.c:75:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   75 |      update(i << 1 | 0, i + 1 << 1 | 0, dp[i << 1 | 0] + xx[i + 1] - xx[i]);
      |                         ~~^~~
E.c:77:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   77 |      update(i << 1 | 0, i + 1 << 1 | 0, dp[i << 1 | 0] + xx[i + 1] - xx[i] - t);
      |                         ~~^~~
E.c:81:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   81 |      update(i << 1 | 1, i + 1 << 1 | 1, dp[i << 1 | 1] + xx[i + 1] - xx[i]);
      |                         ~~^~~
E.c:83:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   83 |      update(i << 1 | 1, i + 1 << 1 | 1, dp[i << 1 | 1] + xx[i + 1] - xx[i] - t);
      |                         ~~^~~
E.c:87:11: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   87 |  if (dp[n - 1 << 1 | 0] == -1 && dp[n - 1 << 1 | 1] == -1) {
      |         ~~^~~
E.c:87:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   87 |  if (dp[n - 1 << 1 | 0] == -1 && dp[n - 1 << 1 | 1] == -1) {
      |                                     ~~^~~
E.c:91:11: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   91 |  u = dp[n - 1 << 1 | 0] != -1 ? n - 1 << 1 | 0 : n - 1 << 1 | 1;
      |         ~~^~~
E.c:91:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   91 |  u = dp[n - 1 << 1 | 0] != -1 ? n - 1 << 1 | 0 : n - 1 << 1 | 1;
      |                                 ~~^~~
E.c:91:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   91 |  u = dp[n - 1 << 1 | 0] != -1 ? n - 1 << 1 | 0 : n - 1 << 1 | 1;
      |                                                  ~~^~~
E.c:40:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d%d%d%d", &x_, &n1, &n2, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
E.c:42:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d", &xx1[i]);
      |   ^~~~~~~~~~~~~~~~~~~~
E.c:45:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d", &xx2[i]);
      |   ^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 27 / 27
• Subtask 5: 23 / 23