Submission #984492

#	Time	Username	Problem	Language	Result	Execution time	Memory
984492		Mr_Ph	Painting Walls (APIO20_paint)	C++17	0 / 100	1 ms	348 KiB

paint

#include "paint.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
int minimumInstructions(int n,int m,int k,vector<int>c,vector<int>a,vector<vector<int>>b)
{
    vector<vector<int>>mp(k);
    for(int i=0;i<m;i++)
    {  
        for(int j=0;j<b[i].size();j++)
            mp[b[i][j]].push_back(i);
    }
    vector<int>arr(k);
    vector<int>temparr(k);
    vector<int>valid(n);
    for(int i=0;i<n;i++)
    {  
        for(int j=0;j<mp[c[i]].size();j++)
        {
            int x=mp[c[i]][j]-1;
            if(x<0)x=m-1;
            temparr[mp[c[i]][j]]=min(arr[x]+1,m);
        }
        if(i)
        {
            for(int j=0;j<mp[c[i-1]].size();j++)
                arr[mp[c[i-1]][j]]=0;
        }
        for(int j=0;j<mp[c[i]].size();j++)
        {
            arr[mp[c[i]][j]]=temparr[mp[c[i]][j]];
            if(arr[mp[c[i]][j]]==m){
                // cout<<i<<endl;
                assert((i-m+1)>=0);
                valid[i-m+1]=1;
            }
            temparr[mp[c[i]][j]]=0;
        }
    }
    // for(int i=0;i<n;i++)cout<<valid[i]<<" ";
    // cout<<endl;
    vector<int>dp(n);
    for(int i=0;i<n;i++)dp[i]=1e9;
    priority_queue<pair<int,int>>pq;
    pq.push({0,0});
    for(int i=0;i<n;i++)
    {
        while(pq.size()&&pq.top().second<(i-1))
            pq.pop();
        if(!pq.size())break;
        // cout<<i<<" ";
        int x=-pq.top().first;
        if(valid[i])
        {
            dp[i+m-1]=min(dp[i+m-1],x+1);
            pq.push({-dp[i+m-1],i+m-1});
        }
    }
    if(dp[n-1]>=1e9)return -1;
    else return dp[n-1];
}

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:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |         for(int j=0;j<b[i].size();j++)
      |                     ~^~~~~~~~~~~~
paint.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int j=0;j<mp[c[i]].size();j++)
      |                     ~^~~~~~~~~~~~~~~~
paint.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for(int j=0;j<mp[c[i-1]].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~~
paint.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int j=0;j<mp[c[i]].size();j++)
      |                     ~^~~~~~~~~~~~~~~~

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