Submission #752677

#	Time	Username	Problem	Language	Result	Execution time	Memory
752677		benjaminkleyn	Painting Walls (APIO20_paint)	C++17	0 / 100	1 ms	340 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;

struct section
{
    // used to store a segment of the wall which i know can be painted nicely.
    int x, y, cnt;
    // we can do this for 0 <= l < cnt, instead of just M.
};

bool operator<(const section &X, const section &Y)
{
    return X.y + X.cnt < Y.y + Y.cnt;
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B)
{
    vector<set<int>> b(M);
    for (int i = 0; i < M; i++)
        b[i] = set<int>(B[i].begin(), B[i].end());

    vector<section> sections1;
    vector<section> sections2;
    for (int offset = 0; offset < M; offset++)
    {
        int cnt = 0;
        for (int i = 0; i < N; i++)
        {
            if (b[(i + offset) % M].find(C[i]) == b[(i + offset) % M].end())
            {
                if (cnt >= M)
                {
                    sections1.push_back({(i - cnt + offset) % M, i - cnt, cnt});
                    sections2.push_back({(i - cnt + offset) % M, i - cnt, cnt});
                }
                cnt = 0;
            }
            else
                cnt++;
        }
        if (cnt >= M)
        {
            sections1.push_back({(N - cnt + offset) % M, N - cnt, cnt});
            sections2.push_back({(N - cnt + offset) % M, N - cnt, cnt});
        }
    }

    sort(sections2.begin(), sections2.end());
    sort(sections1.begin(), sections1.end(), 
        [] (const section &X, const section &Y)
        {
            return X.y < Y.y;
        }
    );

    vector<bool> done(N, false);
    int ans = 0;
    set<section> sections;
    int l = 0, r = 0;
    for (int i = 0; i < N; i++)
    {
        while (r < sections1.size() && sections1[r].y == i)
            sections.insert(sections1[r++]);

        if (!done[i])
        {
            auto [x, y, cnt] = *sections.rbegin();
            ans++;
            for (int j = i; j < N && j < y + cnt && j < i + M; j++)
                done[j] = true;
        }

        while (l < r && sections2[l].y + sections2[l].cnt - 1 == i)
            sections.erase(sections2[l++]);
    }
    
    return ans;
}

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:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<section>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         while (r < sections1.size() && sections1[r].y == i)
      |                ~~^~~~~~~~~~~~~~~~~~

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