Submission #569816

#	Time	Username	Problem	Language	Result	Execution time	Memory
569816		aryan12	Painting Walls (APIO20_paint)	C++17	0 / 100	1 ms	300 KiB

paint

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

int minimumInstructions(int N, int M, int K, vector<int> colors, vector<int> num, vector<vector<int> > likes) 
{
    vector<vector<int> > dp(2, vector<int> (M, -1e9));
    vector<int> likings[K];
    for(int contractor = 0; contractor < M; contractor++)
    {
        for(int j = 0; j < num[contractor]; j++)
        {
            likings[likes[contractor][j]].push_back(contractor);
        }
    }
    vector<int> start_pos;
    for(int i = N - 1; i >= 0; i--)
    {
        int omk_cur = i % 2, omk_prev = (i + 1) % 2;
        bool flag = false;
        for(int j = 0; j < likings[colors[i]].size(); j++)
        {
            int cur = likings[colors[i]][j];
            if(i == N - 1 || dp[omk_prev][(cur + 1) % M] == -1e9)
            {
                dp[omk_cur][cur] = 1;
            }
            else
            {
                dp[omk_cur][cur] = dp[omk_prev][(cur + 1) % M] + 1;
            }
            if(dp[omk_cur][cur] >= M && i <= N - M && !flag)
            {
                start_pos.push_back(i);
                flag = true;
            }
        }
        // for(int j = 0; j < M; j++)
        // {
        //     if(likings[j].count(colors[i]))
        //     {
        //         if(i == N - 1 || dp[i + 1][(j + 1) % M] == -1e9)
        //         {
        //             dp[i][j] = 1;
        //         }
        //         else
        //         {
        //             dp[i][j] = dp[i + 1][(j + 1) % M] + 1;
        //         }
        //     }
        //     // cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << "\n";
        // }
        // cout << "\n\n\n\n";
    }
    // vector<int> start_pos;
    // for(int i = N - M; i >= 0; i--)
    // {
    //     for(int j = 0; j < M; j++)
    //     {
    //         if(dp[i][j] >= M)
    //         {
    //             start_pos.push_back(i);
    //             // cout << i << "\n";
    //             break;
    //         }
    //     }
    // }
    int ans = 0;
    int min_x = N;
    for(int i = 0; i < start_pos.size(); i++)
    {
        // cout << "start_pos[i] = " << start_pos[i] << ", M = " << M << ", minx = " << min_x << "\n";
        if(start_pos[i] + M - 1 < min_x - 1)
        {
            return -1;
        }
        if(i == start_pos.size() - 1 || start_pos[i + 1] + M - 1 < min_x - 1 || start_pos[i] == 0)
        {
            min_x = start_pos[i];
            ans++;
        }
    }
    if(min_x != 0) return -1;
    return ans;
}

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:21:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int j = 0; j < likings[colors[i]].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < start_pos.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~
paint.cpp:77:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         if(i == start_pos.size() - 1 || start_pos[i + 1] + M - 1 < min_x - 1 || start_pos[i] == 0)
      |            ~~^~~~~~~~~~~~~~~~~~~~~~~

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