oj.uz

Submission #401732

# Submission time Handle Problem Language Result Execution time Memory
401732 2021-05-10T18:26:38 Z blue Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 204 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -