Submission #401732

#TimeUsernameProblemLanguageResultExecution timeMemory
401732bluePainting Walls (APIO20_paint)C++17
0 / 100
1 ms204 KiB
#include "paint.h" #include <vector> #include <deque> #include <set> using namespace std; /* f(k) <= √400000 = ~650 For every color, we can compute the list of contractors who can paint it. For every wall segment, we can compute the list of contractors who can paint it. */ int minimumInstructions( int N, int M, int K, vector<int> C, vector<int> A, vector< vector<int> > B) { //N = number of wall segments //M = number of contractors //K = number of colors //C[i] = intended color of i'th segment //A[i] = B[i].size //B[i] = set of colors that contractor i can work with vector<int> col_workers[K]; //list of workers that can work with color k for(int j = 0; j < M; j++) for(int b: B[j]) col_workers[b].push_back(j); vector<int> startpos[N]; //list of starting positions (position of worker 0) from which color i can be painted for(int i = 0; i < N; i++) for(int w: col_workers[C[i]]) { // cerr << i << ' ' << C[i] << ' ' << w << ' ' << i-w << ' ' << i-w+M << '\n'; if(0 <= i-w) startpos[i].push_back(i-w); if(w != 0 && i-w+M < N) startpos[i].push_back(i-w+M); } int res = 0; // for(int i = 0; i < N; i++) // { // cerr << i << ": "; // for(int s: startpos[i]) cerr << s << ' '; // cerr << '\n'; // } vector<int> can_start(N, 0); //whether the M contractors can paint i ... i+M-1 in one operation vector<int> start_ct(N, 0); for(int i = 0; i < M; i++) for(int x: startpos[i]) start_ct[x]++; int mx_start = 0; for(int i = 1; i < N; i++) { if(start_ct[i] >= start_ct[mx_start]) mx_start = i; } can_start[0] = (start_ct[mx_start] == M); for(int i = 1; i+M-1 < N; i++) { for(int x: startpos[i-1]) { start_ct[x]--; // cerr << x << "--\n"; } mx_start = -1; for(int x: startpos[i+M-1]) { start_ct[x]++; // cerr << x << "++\n"; if(mx_start == -1 || start_ct[x] >= start_ct[mx_start]) mx_start = x; } // cerr << "pos i = " << i << '\n'; // for(int j = 0; j < N; j++) cerr << start_ct[j] << ' '; // cerr << '\n'; if(start_ct[mx_start] == M) can_start[i] = 1; } // for(int i = 0; i < N; i++) cerr << can_start[i] << ' '; // cerr << '\n'; if(can_start[0] == 0) return -1; deque<int> S; for(int i = 0; i < N; i++) if(can_start[i]) S.push_back(i); // for(int q:S) cerr << q << ' '; // cerr << '\n'; vector<int> dp(N, 1e9); for(int i = 0; i < M; i++) dp[i] = 1; for(int i = M; i < N; i++) { // cerr << "i = " << i << '\n'; // for(int s:S) cerr << s << ' '; // cerr << '\n'; while(S.size() > 1 && S[0]+M-1 < i) S.pop_front(); // for(int s:S) cerr << s << ' '; // cerr << '\n'; if(S.empty() || S[0] + M - 1 < i) return -1; dp[i] = dp[S.front() - 1] + 1; } return dp[N-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:41:9: warning: unused variable 'res' [-Wunused-variable]
   41 |     int res = 0;
      |         ^~~
#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...