제출 #401756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401756		blue	벽 칠하기 (APIO20_paint)	C++17	100 / 100	1409 ms	15712 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 n, m, k;
vector<int>* c;
vector<int>* a;
vector< vector<int> >* b;
vector<int> col_workers[100000];
vector<int> start_ct(100000, 0);

vector<int> compute_startpos(int i)
{
    vector<int> temp;
    for(int w: col_workers[(*c)[i]])
    {
        // cerr << i << ' ' << C[i] << ' ' << w << ' ' << i-w << ' ' << i-w+M << '\n';
        if(0 <= i-w)
            temp.push_back(i-w);

        if(w != 0 && i-w+m < n)
            temp.push_back(i-w+m);
    }
    return temp;
}

void add_startpos(int i, int a)
{
    for(int w: col_workers[(*c)[i]])
    {
        // cerr << i << ' ' << C[i] << ' ' << w << ' ' << i-w << ' ' << i-w+M << '\n';
        if(0 <= i-w)
            start_ct[i-w] += a;

        if(w != 0 && i-w+m < n)
            start_ct[i-w+m] += a;
    }
}


int minimumInstructions(
    int N, int M, int K, vector<int> C, vector<int> A, vector< vector<int> > B)
{
    n = N;
    m = M;
    k = K;
    c = &C;
    a = &A;
    b = &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

    for(int i = 0; i < M; i++)
    {
        add_startpos(i, +1);
    }

    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++)
    {
        add_startpos(i-1, -1);

        mx_start = -1;
        vector<int> temp = compute_startpos(i+M-1);
        for(int x: temp)
        {
            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 || S[0] > i)
            return -1;

        dp[i] = dp[S.front() - 1] + 1;
    }

    return dp[N-1];
}

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:82:9: warning: unused variable 'res' [-Wunused-variable]
   82 |     int res = 0;
      |         ^~~

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