Submission #401732

#	Time	Username	Problem	Language	Result	Execution time	Memory
401732		blue	Painting Walls (APIO20_paint)	C++17	0 / 100	1 ms	204 KiB

paint

#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;
      |         ^~~

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