Submission #981935

#	Time	Username	Problem	Language	Result	Execution time	Memory
981935		Abito	Painting Walls (APIO20_paint)	C++17	100 / 100	413 ms	291660 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define pb push_back
#define ep insert
using namespace std;
const int N=1e5+5,M=700;
int c[N],dp[N],r[N][M];
vector<int> v[N];
int minimumInstructions(
    int n, int m, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B){
    for (int i=1;i<=n;i++) c[i]=C[i-1]+1;
    for (int i=0;i<m;i++) for (auto u:B[i]) v[u+1].pb(i);
    for (int i=1;i<=n;i++) if (v[c[i]].empty()) return -1;;
    for (int i=1;i<=n;i++) for (int j=0;j<v[c[i]].size();j++) r[i][j]=i;
    for (int i=n-1;i;i--){
        int k=0;
        for (int j=0;j<v[c[i]].size() && k<v[c[i+1]].size();j++){
            while (k<v[c[i+1]].size() && v[c[i+1]][k]<=v[c[i]][j]) k++;
            if (k==v[c[i+1]].size()) break;
            if ((v[c[i]][j]+1)%m==v[c[i+1]][k]) r[i][j]=r[i+1][k];
        }
        if (v[c[i]].back()==m-1 && v[c[i+1]][0]==0) r[i][v[c[i]].size()-1]=r[i+1][0];
    }
    multiset<int> s;
    for (int i=1;i<=n;i++) dp[i]=N;
    for (int i=1;i<m;i++) s.ep(N);
    s.ep(0);
    for (int i=n;i;i--){
        if (i+m>n+1) continue;
        bool ok=false;
        for (int j=0;j<v[c[i]].size();j++) ok|=(r[i][j]-i>=m-1);
        if (ok) dp[i]=*s.begin()+1;
        s.ep(dp[i]);
        s.erase(s.find(dp[i+m]));
    }
    if (dp[1]>=N) return -1;
    return dp[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:15:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i=1;i<=n;i++) for (int j=0;j<v[c[i]].size();j++) r[i][j]=i;
      |                                         ~^~~~~~~~~~~~~~~
paint.cpp:18:23: 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<v[c[i]].size() && k<v[c[i+1]].size();j++){
      |                      ~^~~~~~~~~~~~~~~
paint.cpp:18:43: 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<v[c[i]].size() && k<v[c[i+1]].size();j++){
      |                                          ~^~~~~~~~~~~~~~~~~
paint.cpp:19:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             while (k<v[c[i+1]].size() && v[c[i+1]][k]<=v[c[i]][j]) k++;
      |                    ~^~~~~~~~~~~~~~~~~
paint.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |             if (k==v[c[i+1]].size()) break;
      |                 ~^~~~~~~~~~~~~~~~~~
paint.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int j=0;j<v[c[i]].size();j++) ok|=(r[i][j]-i>=m-1);
      |                      ~^~~~~~~~~~~~~~~

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