Submission #982442

#	Time	Username	Problem	Language	Result	Execution time	Memory
982442		phoenix	Painting Walls (APIO20_paint)	C++17	100 / 100	1161 ms	506528 KiB

paint

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

using namespace std;
using ll = long long;

int n, m;

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

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

vector<int> inst[K];

vector<vector<int>> g;
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());
    
    g.resize(n + 1);
    for (int i = 0; i < n; i++) 
        g[i] = inst[C[i]];

    auto get = [&](int i, int j) -> int {
        int x = lower_bound(g[i].begin(), g[i].end(), j) 
                - g[i].begin();
            
        if (x != (int)g[i].size() && g[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)g[i].size());

        for (int j = 0; j < (int)f[i].size(); j++) {
            f[i][j] = 1 + get(i + 1, (g[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;
    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:73:9: warning: unused variable 'res' [-Wunused-variable]
   73 |     int res = 1e9;
      |         ^~~

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