# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
401732 | blue | Painting Walls (APIO20_paint) | C++17 | 1 ms | 204 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |