Submission #481172

#	Time	Username	Problem	Language	Result	Execution time	Memory
481172		rainboy	Grudanje (COCI19_grudanje)	C11	70 / 70	51 ms	1148 KiB

grudanje

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

#define N	100000
#define Q	100000
#define A	26

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

char cc[N + 1]; int pp[N], ll[N], n;

int solve(int k) {
	static int prev[A];
	int i, j;

	memset(prev, -1, A * sizeof *prev);
	for (j = 0, i = -1; j < n; j++) {
		if (pp[j] > k) {
			int a = cc[j] - 'a';

			i = max(i, prev[a]), prev[a] = j;
		}
		if (ll[j] <= i)
			return 0;
	}
	return 1;
}

int main() {
	int q, i, j, p, lower, upper;

	scanf("%s%d", cc, &q), n = strlen(cc);
	for (i = 0; i < n; i++)
		ll[i] = i;
	while (q--) {
		scanf("%d%d", &i, &j), i--, j--;
		ll[j] = min(ll[j], i);
	}
	for (p = 1; p <= n; p++) {
		scanf("%d", &i), i--;
		pp[i] = p;
	}
	lower = -1, upper = n;
	while (upper - lower > 1) {
		int k = (lower + upper) / 2;

		if (solve(k))
			upper = k;
		else
			lower = k;
	}
	printf("%d\n", upper);
	return 0;
}

Compilation message (stderr)

grudanje.c: In function 'main':
grudanje.c:33:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%s%d", cc, &q), n = strlen(cc);
      |  ^~~~~~~~~~~~~~~~~~~~~
grudanje.c:37:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
grudanje.c:41:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d", &i), i--;
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7