Submission #464902

#	Time	Username	Problem	Language	Result	Execution time	Memory
464902		alextodoran	Painting Walls (APIO20_paint)	C++17	0 / 100	1 ms	332 KiB

paint

#include <bits/stdc++.h>

#include "paint.h"

using namespace std;

const int INF = INT_MAX / 2;

mt19937 rng(time(0));

int rngSeg (int l, int len)
{
    return l + rng() % len;
}

int minimumInstructions(int N, int M, int K, vector <int> C, vector <int> A, vector <vector <int>> B)
{
    vector <vector <int>> likers (K);
    for(int i = 0; i < M; i++)
        for(int j = 0; j < A[i]; j++)
            likers[B[i][j]].push_back(i);

    function <bool (int, int)> likes = [&] (int worker, int color)
    {
        int l = 0, r = A[worker];
        while(l < r)
        {
            int mid = (l + r) / 2;
            if(B[worker][mid] < color)
                l = mid + 1;
            else
                r = mid;
        }

        return (l < A[worker] && B[worker][l] == color);
    };

    vector <bool> possible (N - M + 1);
    for(int l = 0; l + M - 1 < N; l++)
    {
        int t = rngSeg(l, M);
        for(int it = 1; it <= 100; it++)
        {
            int cand = rngSeg(l, M);
            if((int) likers[C[cand]].size() < (int) likers[C[t]].size())
                t = cand;
        }

        possible[l] = false;
        for(int x : likers[C[t]])
        {
            int p = x - (t - l);
            if(p < 0)
                p += M;
            if(p >= M)
                continue;

            bool match = true;
            for(int i = 0; i < M; i++)
                if(likes((i + p) % M, C[l + i]) == false)
                    match = false;

            if(match == true)
            {
                possible[l] = true;
                break;
            }
        }
    }

    vector <int> minPref (N, INF);
    deque <int> dq;

    minPref[M - 1] = INF;
    if(possible[0] == true)
        minPref[M - 1] = 1;

    for(int i = M; i < N; i++)
    {
        if(dq.empty() == false && dq.front() < i - M)
            dq.pop_front();

        while(dq.empty() == false && minPref[i - 1] <= minPref[dq.back()])
            dq.pop_back();

        dq.push_back(i - 1);

        if(possible[i - M + 1] == true)
        {
            if(minPref[dq.front()] != INF)
                minPref[i] = minPref[dq.front()] + 1;
        }
    }

    if(minPref[N - 1] == INF)
        return -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:18:36: warning: control reaches end of non-void function [-Wreturn-type]
   18 |     vector <vector <int>> likers (K);
      |                                    ^

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