Submission #434697

#TimeUsernameProblemLanguageResultExecution timeMemory
434697dqhungdlPainting Walls (APIO20_paint)C++17
0 / 100
14 ms14568 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int MAX=1e5+5; vector<int> companies[MAX],g[MAX],f[MAX]; int minimumInstructions( int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) { for(int i=0;i<M;i++) for(int j=0;j<A[i];j++) companies[B[i][j]].push_back(i); for(int i=0;i<N;i++) { g[i]=companies[C[i]]; f[i].resize(g[i].size()); } vector<bool> canStart(N); for(int i=0;i<g[N-1].size();i++) f[N-1][i]=N-1; for(int i=N-2;i>=0;i--) { int cur=0; for(int j=0;j<g[i].size();j++) { int nextValue=(g[i][j]+1)%M; if(nextValue==0) f[i][j]=(g[i+1][0]==0?f[i+1][0]:i); else { while(cur<g[i+1].size()&&g[i+1][cur]<nextValue) cur++; if(cur<g[i+1].size()&&g[i+1][cur]==nextValue) f[i][j]=f[i+1][cur]; else f[i][j]=i; } } } for(int i=0;i<N;i++) for(int j=0;j<g[i].size();j++) if(f[i][j]-i+1>=M) canStart[i]=true; int cur=-1,lastPos=0,rs=0; while(lastPos<N) { int found=-1; for(int i=lastPos;i>cur;i--) if(canStart[i]) { found=i; break; } if(found==-1) return -1; lastPos=found+M; cur=found; rs++; } return rs; }

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:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0;i<g[N-1].size();i++)
      |              ~^~~~~~~~~~~~~~
paint.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int j=0;j<g[i].size();j++) {
      |               ~^~~~~~~~~~~~
paint.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(cur<g[i+1].size()&&g[i+1][cur]<nextValue)
      |           ~~~^~~~~~~~~~~~~~
paint.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if(cur<g[i+1].size()&&g[i+1][cur]==nextValue)
      |        ~~~^~~~~~~~~~~~~~
paint.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j=0;j<g[i].size();j++)
      |               ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...