Submission #1089710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089710		raphaelp	Painting Walls (APIO20_paint)	C++14	100 / 100	684 ms	14760 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int nex(int x, int N)
{
    return (x + 1) % N;
}
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B)
{
    vector<int> dp(N, N + 1);
    dp[0] = 0;
    int buff2 = 1;
    vector<vector<int>> colors(K);
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < A[i]; j++)
        {
            colors[B[i][j]].push_back(i);
        }
    }
    deque<pair<int, int>> cur, next;
    for (int i = 0; i < N; i++)
    {
        next.clear();
        for (int j = 0; j < colors[C[i]].size(); j++)
        {
            while (!cur.empty() && cur.front().second <= colors[C[i]][j])
            {
                if (cur.front().second == colors[C[i]][j])
                {
                    if (cur.front().first >= M - 1)
                        while (buff2 <= i + 1)
                        {
                            if (dp[i - M + 1] == N + 1)
                                return -1;
                            if (buff2 == N)
                                return dp[i - M + 1] + 1;
                            dp[buff2] = dp[i - M + 1] + 1;
                            buff2++;
                        }
                    if (nex(colors[C[i]][j], M))
                        next.push_back({cur.front().first + 1, nex(colors[C[i]][j], M)});
                    else
                        next.push_front({cur.front().first + 1, nex(colors[C[i]][j], M)});
                }
                cur.pop_front();
            }
            if (next.empty() || (next.back().second != nex(colors[C[i]][j], M) && next.front().second != nex(colors[C[i]][j], M)))
            {
                if (M == 1)
                {
                    if (dp[i] == N + 1)
                        return -1;
                    if (i == N - 1)
                        return dp[i] + 1;
                    dp[i + 1] = dp[i] + 1;
                    buff2++;
                }
                if (nex(colors[C[i]][j], M))
                    next.push_back({1, nex(colors[C[i]][j], M)});
                else
                    next.push_front({1, nex(colors[C[i]][j], M)});
            }
        }
        swap(next, cur);
    }
    return -1;
}
/*int main()
{
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> A(M), C(N);
    vector<vector<int>> B(M);
    for (int i = 0; i < N; i++)
        cin >> C[i];
    for (int i = 0; i < M; i++)
    {
        cin >> A[i];
        for (int j = 0; j < A[i]; j++)
        {
            B[i].push_back(0);
            cin >> B[i][j];
        }
    }
    cout << minimumInstructions(N, M, K, C, A, B);
}*/

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:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int j = 0; j < colors[C[i]].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~

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