Submission #979738

#	Time	Username	Problem	Language	Result	Execution time	Memory
979738		vjudge1	Painting Walls (APIO20_paint)	C++17	0 / 100	2 ms	2652 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;
using ll = long long;

const int N1 = 20200;
const int M1 = 2020;

int n, m;

const int N = 100100;
const int K = 100100;

bool able[N] = {};
int to[N] = {};

vector<int> inst[K];

vector<vector<int>> f;

int minimumInstructions(
    int N, int M, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B) {
    n = N,
    m = M;

    for (int i = 0; i < m; i++) {
        for (int x : B[i]) {
            inst[x].push_back(i); 
        }
    }
    for (int i = 0; i < K; i++) 
        sort(inst[i].begin(), inst[i].end());

    auto get = [&](int i, int j) -> int {
        if (i == n) return 0;
        int x = lower_bound(inst[C[i]].begin(), inst[C[i]].end(), j) 
                - inst[C[i]].begin();
            
        if (x != (int)inst[C[i]].size() && inst[C[i]][x] == j)
            return f[i][x];
        return 0;
    };

    f.resize(n + 1);

    for (int i = n - 1; i >= 0; i--) {
        f[i].resize((int)inst[C[i]].size() + 1);

        for (int j = 0; j < (int)f[i].size(); j++) {
            f[i][j] = 1 + get(i + 1, (inst[C[i]][j] + 1) % m);
        }
    }
    for (int i = 0; i <= n - m; i++) {
        for (int c : f[i])
            if (c >= m)
                able[i] = true;
    }
    
    {
        if (!able[0]) return -1;
        
        int nxt = 0, w = 0;
        for (int i = 0; i < n; i++) {
            if (able[i]) 
                nxt = (i + m);
            to[i] = max(nxt, i);
        }
    }

    int res = 1e9;

    int x = 0, ans = 0;
    while (x < n && x != to[x]) {
        ans++;
        x = to[x];
    }
    if (x == n) return ans;
    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:64:22: warning: unused variable 'w' [-Wunused-variable]
   64 |         int nxt = 0, w = 0;
      |                      ^
paint.cpp:72:9: warning: unused variable 'res' [-Wunused-variable]
   72 |     int res = 1e9;
      |         ^~~

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