oj.uz

Submission #984492

# Submission time Handle Problem Language Result Execution time Memory
984492 2024-05-16T17:42:40 Z Mr_Ph Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 348 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -