Submission #1177391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177391		anmattroi	Painting Walls (APIO20_paint)	C++17	100 / 100	367 ms	255184 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;

const int B = 632;

vector<int> colorLikers[maxn], Nex[maxn];

int Sekijo[maxn];

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 j = 0; j < A[i]; j++)
            colorLikers[B[i][j]].emplace_back(i);

    if (1) {
        int curColor = C[N-1];
        int sz = colorLikers[curColor].size();
        if (sz == 0) return -1;
        Nex[N-1].assign(sz, N-1);
    }
    for (int o = N-2; o >= 0; o--) {
        int curColor = C[o];
        int sz = colorLikers[curColor].size(),
            szTwo = colorLikers[C[o+1]].size();
        if (sz == 0) return -1;
        Nex[o].assign(sz, o);
        for (int i = 0, it = 0; i < sz; i++) {
            int curPos = colorLikers[curColor][i],
                nexPos = (curPos+1)%M;
            if (nexPos < curPos) it = 0;
            while (it < szTwo && colorLikers[C[o+1]][it] < nexPos) ++it;
            if (it == szTwo || colorLikers[C[o+1]][it] != nexPos) continue;
            Nex[o][i] = Nex[o+1][it];
        }
    }
    for (int i = 0; i <= N-M; i++) {
        int mx = i;
        for (int x : Nex[i]) mx = max(mx, x);
        Sekijo[i] = (mx-i+1 >= M);
    }

    if (!Sekijo[0] || !Sekijo[N-M]) return -1;
    int last = 1, cur = 0, ans = 0;
    while (last <= N) {
        int lim = last;
        for (; cur < lim; cur++)
            if (Sekijo[cur])
                last = cur + M + 1;

        if (lim == last) return -1;
        ++ans;
    }
    return ans;
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

3
*/

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