Submission #464920

#	Time	Username	Problem	Language	Result	Execution time	Memory
464920		alextodoran	Painting Walls (APIO20_paint)	C++17	0 / 100	1 ms	204 KiB

paint

#include <bits/stdc++.h>

#include "paint.h"

using namespace std;

const int INF = INT_MAX / 2;

int minimumInstructions(int N, int M, int K, vector <int> C, vector <int> A, vector <vector <int>> B)
{
    vector <int> liker (K, -1);
    for(int i = 0; i < M; i++)
        for(int j = 0; j < A[i]; j++)
            liker[B[i][j]] = i;
    for(int i = 0; i < N; i++)
        if(liker[C[i]] == -1)
            return -1;

    for(int i = 0; i < N; i++)
        C[i] = liker[C[i]];

    vector <int> magic (N - 1);
    for(int i = 0; i < N - 1; i++)
    {
        int diff = C[i + 1] - C[i];
        magic[i] = (diff == 1 || diff == 1 - M);
    }
    for(int i = 1; i < N - 1; i++)
        magic[i] += magic[i - 1];

    vector <bool> possible (N - M + 1);

    for(int l = 0; l + M - 1 < N; l++)
    {
        int seg = 0;
        if(l + M - 1 > 0)
            magic[l + M - 1 - 1];
        if(l > 0)
            seg -= magic[l - 1];
        possible[l] = (seg == M - 1);
    }

    vector <int> minPref (N, INF);
    deque <int> dq;

    minPref[M - 1] = INF;
    if(possible[0] == true)
        minPref[M - 1] = 1;

    for(int i = M; i < N; i++)
    {
        if(dq.empty() == false && dq.front() < i - M)
            dq.pop_front();

        while(dq.empty() == false && minPref[i - 1] <= minPref[dq.back()])
            dq.pop_back();

        dq.push_back(i - 1);

        if(possible[i - M + 1] == true)
        {
            if(minPref[dq.front()] != INF)
                minPref[i] = minPref[dq.front()] + 1;
        }
    }

    if(minPref[N - 1] == INF)
        return -1;
    return minPref[N - 1];
}

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