Submission #430147

#	Time	Username	Problem	Language	Result	Execution time	Memory
430147		marcipan5000	Painting Walls (APIO20_paint)	C++14	0 / 100	6 ms	5328 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

int n,m,k;
vector<int> c;
vector<int> a;
vector<vector<int> > b;
vector<vector<int> > sz;
int co[100001];
int mc;
vector<int> ans;

int bias(int a,int b) {
    return((a-b+n*m)%m);
}

int minimumInstructions(int N1, int M1, int K1, vector<int> C1, vector<int> A1, vector<vector<int> > B1) {
    n=N1;
    m=M1;
    k=K1;
    c=C1;
    a=A1;
    b=B1;
    sz.resize(k);
    for (int i=0;i<b.size();i++) {
        for (int j=0;j<b[i].size();j++) {
            sz[b[i][j]].push_back(i);
        }
    }
    for (int i=0;i<m;i++) {
        for (int j=0;j<sz[c[i]].size();j++) {
            co[bias(sz[c[i]][j],i)]++;
            if (co[bias(sz[c[i]][j],i)]==m) {
                mc++;
            }
        }
    }
    if (mc>0) {
        ans.push_back(0);
    }
    for (int i=m;i<n;i++) {
        for (int j=0;j<sz[c[i-m]].size();j++) {
            co[bias(sz[c[i-m]][j],i-m)]--;
            if (co[bias(sz[c[i-m]][j],i-m)]==m-1) {
                mc--;
            }
        }
        for (int j=0;j<sz[c[i]].size();j++) {
            co[bias(sz[c[i]][j],i)]++;
            if (co[bias(sz[c[i]][j],i)]==m) {
                mc++;
            }
        }
        if (mc>0) {
            ans.push_back(i-m+1);
        }
    }
    int l=0;
    int h=0;
    int an=0;
    while (h<n) {
        while ((l<ans.size())&&(ans[l]<=h)) {
            l++;
        }
        if (ans[l-1]==h-m) {
            return(-1);
        }
        h=ans[l-1]+m;
        an++;
    }
    return(an);
}

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:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i=0;i<b.size();i++) {
      |                  ~^~~~~~~~~
paint.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int j=0;j<b[i].size();j++) {
      |                      ~^~~~~~~~~~~~
paint.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int j=0;j<sz[c[i]].size();j++) {
      |                      ~^~~~~~~~~~~~~~~~
paint.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int j=0;j<sz[c[i-m]].size();j++) {
      |                      ~^~~~~~~~~~~~~~~~~~
paint.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int j=0;j<sz[c[i]].size();j++) {
      |                      ~^~~~~~~~~~~~~~~~
paint.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while ((l<ans.size())&&(ans[l]<=h)) {
      |                 ~^~~~~~~~~~~

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