Submission #387076

#	Time	Username	Problem	Language	Result	Execution time	Memory
387076		rainboy	Painting Walls (APIO20_paint)	C++11	100 / 100	964 ms	13220 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <vector>

const int N = 100000, C = 100000, M = 50000;

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

int *ej[C], eo[C];

void append(int a, int j) {
	int o = eo[a]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[a] = (int *) realloc(ej[a], o * 2 * sizeof *ej[a]);
	ej[a][o] = j;
}

int minimumInstructions(int n, int m, int c, std::vector<int> aa, std::vector<int> kk, std::vector<std::vector<int>> aaa) {
	static int ll[M];
	static char can[N];
	int a, h, i, i_, j, ans;

	for (a = 0; a < c; a++)
		ej[a] = (int *) malloc(2 * sizeof *ej[a]);
	for (j = 0; j < m; j++)
		for (h = 0; h < kk[j]; h++)
			append(aaa[j][h], j);
	for (i = 0; i < n; i++) {
		int o;

		if (i >= m) {
			a = aa[i - m];
			for (o = eo[a]; o--; ) {
				j = ej[a][o];
				ll[(j - i % m + m) % m]--;
			}
		}
		a = aa[i];
		for (o = eo[a]; o--; ) {
			j = ej[a][o];
			if (++ll[(j - i % m + m) % m] == m)
				can[i - m + 1] = 1;
		}
	}
	if (!can[0])
		return -1;
	i = 0, ans = 1;
	while (i + m < n) {
		for (i_ = min(i + m, n - 1); i_ > i; i_--)
			if (can[i_])
				break;
		if (i_ == i)
			return -1;
		i = i_, ans++;
	}
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'void append(int, int)':
paint.cpp:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37