Submission #386334

#	Time	Username	Problem	Language	Result	Execution time	Memory
386334		leinad2	Painting Walls (APIO20_paint)	C++17	63 / 100	1569 ms	16108 KiB

paint

#include<bits/stdc++.h>
using namespace std;
vector<vector<int> >B;
int f(int a, int m){a%=m;if(a<0)a+=m;return a;}
int minimumInstructions(int N, int M, int K, vector<int>C, vector<int>A, vector<vector<int> >bB)
{
    B=bB;
    int i, j, k;
    vector<int>X;X.resize(N);
    vector<vector<int> >S;S.resize(K);
    vector<int>cnt;cnt.resize(M);
    int chk=0;
    for(i=0;i<M;i++)
    {
        for(j=0;j<A[i];j++)
        {
            S[B[i][j]].push_back(i);
        }
    }
    for(i=0;i<M;i++)
    {
        for(j=0;j<S[C[i]].size();j++)
        {
            int a=f(i-S[C[i]][j], M);
            cnt[a]++;
        }
    }
  for(i=0;i<M;i++)if(cnt[i]==M)chk++;
    if(chk)X[0]=1;
    for(i=1;i<=N-M;i++)
    {
        for(j=0;j<S[C[i-1]].size();j++)
        {
            int a=f(i-1-S[C[i-1]][j], M);
            cnt[a]--;
            if(cnt[a]==M-1)chk--;
        }
        for(j=0;j<S[C[i+M-1]].size();j++)
        {
            int a=f(i+M-1-S[C[i+M-1]][j], M);
            cnt[a]++;if(cnt[a]==M)chk++;
        }
        if(chk)X[i]=1;
    }
    i=0;
    if(X[0]==0||X[N-M]==0)return -1;
    int ans=0;
    while(1)
    {
        if(i==N-M)return ans+1;
        k=-1;
        for(j=i+1;j<=i+M;j++)
        {
            if(X[j])k=j;
        }
        if(k==-1)return -1;
        i=k;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:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(j=0;j<S[C[i]].size();j++)
      |                 ~^~~~~~~~~~~~~~~
paint.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(j=0;j<S[C[i-1]].size();j++)
      |                 ~^~~~~~~~~~~~~~~~~
paint.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(j=0;j<S[C[i+M-1]].size();j++)
      |                 ~^~~~~~~~~~~~~~~~~~~

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