Submission #401946

#TimeUsernameProblemLanguageResultExecution timeMemory
401946faresbasbsPainting Walls (APIO20_paint)C++14
100 / 100
839 ms15084 KiB
#include <bits/stdc++.h> #include "paint.h" using namespace std; int v1[100001],v2[100001],q1[100001],q2[100001],cnt1,cnt2; vector<int> vals[100001]; bitset<100001> bs1,bs2; int minimumInstructions(int n , int m , int K , vector<int> c , vector<int> A , vector<vector<int>> B){ for(int i = 0 ; i < m ; i += 1){ v1[i] = v2[i] = -1000000000; for(auto j : B[i]){ vals[j].push_back(i); } } for(int i : vals[c[n-1]]){ q1[cnt1++] = i; bs1[i] = 1; v1[i] = n-1; } vector<int> all; bool ok = 0; for(auto j : q1){ if(v1[j]-(n-1) >= m-1){ ok = 1; } } if(ok){ all.push_back(n-1); } for(int i = n-2 ; i >= 0 ; i -= 1){ for(auto j : vals[c[i]]){ bs2[j] = 1; if(bs1[(j+1)%m]){ q2[cnt2++] = j; v2[j] = v1[(j+1)%m]; }else{ q2[cnt2++] = j; v2[j] = i; } } for(int j = 0 ; j < cnt1 ; j += 1){ v1[q1[j]] = -1000000000; bs1[q1[j]] = 0; } for(int j = 0 ; j < cnt2 ; j += 1){ v1[q2[j]] = v2[q2[j]]; v2[q2[j]] = -1000000000; q1[j] = q2[j]; bs1[q2[j]] = 1; bs2[q2[j]] = 0; } swap(cnt1,cnt2); cnt2 = 0; bool ok = 0; for(int j = 0 ; j < cnt1 ; j += 1){ if(v1[q1[j]]-i >= m-1){ ok = 1; } } if(ok){ all.push_back(i); } } reverse(all.begin(),all.end()); if(all.size() == 0 || all[0] != 0){ return -1; } int pre = 0 , mx = 0 , cnt = 1; for(int i = 0 ; i < all.size() ; i += 1){ if(pre+m >= all[i]){ mx = all[i]; continue; } if(mx == pre){ return -1; } cnt += 1 , pre = mx; i -= 1; } if(pre+m == n){ return cnt; } pre = mx , cnt += 1; if(pre+m == n){ return cnt; } return -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:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i = 0 ; i < all.size() ; i += 1){
      |                  ~~^~~~~~~~~~~~
#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...