Submission #991990

#	Time	Username	Problem	Language	Result	Execution time	Memory
991990		pubin06	Painting Walls (APIO20_paint)	C++17	100 / 100	893 ms	506604 KiB

paint

#include <bits/stdc++.h>
#define sz(v) (int)(v).size()
using namespace std;

const int MXn = 100005;

vector<int> arr1[MXn], arr2[MXn], nxt[MXn];
int prf[MXn];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    for (int i = 0; i < M; i++) {
    	for (int c: B[i]) arr1[c].emplace_back(i);
    }
    for (int i = 0; i < N; i++) {
    	arr2[i] = arr1[C[i]];
    	nxt[i].resize(sz(arr2[i]));
    }
    for (int j = 0; j < sz(nxt[N - 1]); j++) nxt[N - 1][j] = N - 1;
    for (int i = N - 2; i >= 0; i--) {
    	for (int j = 0; j < sz(nxt[i]); j++) {
    		nxt[i][j] = i;
    		int p = lower_bound(begin(arr2[i + 1]), end(arr2[i + 1]), (arr2[i][j] + 1) % M) - arr2[i + 1].begin();
    		if (p < sz(arr2[i + 1]) && arr2[i + 1][p] == ((arr2[i][j] + 1) % M)) {
    			nxt[i][j] = min(i + M - 1, nxt[i + 1][p]);
    		}
    	}
    }
    for (int i = 0; i <= N - M; i++) {
    	int able = 0;
    	for (int j = 0; j < sz(nxt[i]); j++) {
    		if (nxt[i][j] == i + M - 1) {
    			able = 1;
    			break;
    		}
    	}
    	prf[i] = able;
    	if (i > 0) prf[i] += prf[i - 1];
    }
    
    int ans = -1;
    if (prf[0]) {
    	int tmp = 1;
    	int cur = 0;
	    while (cur < N - M) {
	    	int l = cur + 1, r = min(cur + M, N - M), mid, pos;
	    	int num = prf[r] - prf[l - 1];
	    	if (!num) tmp = -N;
	    	while (l <= r) {
	    		mid = (l + r) >> 1;
	    		if (prf[mid] - prf[cur] == num) {
	    			pos = mid;
	    			r = mid - 1;
	    		} else l = mid + 1;
	    	}
	    	tmp++;
	    	cur = pos;
	    }
	    ans = max(ans, tmp);
    }
	
	return ans;
}

// signed main(void) {
	// int N, M, K;
	// scanf("%d %d %d", &N, &M, &K);
	// vector<int> C(N);
	// for (int i = 0; i < N; ++i) scanf("%d", &C[i]);
	// vector<int> A(M);
	// vector<vector<int>> B(M);
	// for (int i = 0; i < M; ++i) {
		// scanf("%d", &A[i]);
		// B[i].resize(A[i]);
	    // for (int j = 0; j < A[i]; ++j) {
	    	// scanf("%d", &B[i][j]);
	    // }
	// }
	// int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
	// printf("%d\n", minimum_instructions);
// 	
	// return 0;
// }

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:46:35: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |       int num = prf[r] - prf[l - 1];
      |                          ~~~~~~~~~^

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