Submission #967833

#	Time	Username	Problem	Language	Result	Execution time	Memory
967833		Pring	Painting Walls (APIO20_paint)	C++17	100 / 100	119 ms	18260 KiB

paint

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

namespace {
    const int MXN = 100005, INF = 1e9;
    int n, m, k;
    vector<int> c;
    vector<vector<int>> clr;
    vector<vector<int>> ava;
    bitset<MXN> b;
    int val[2][MXN];
    int dp[MXN];
    deque<pii> dq;

    int miku() {
        ava.resize(k);
        FOR(i, 0, m) {
            for (auto &j : clr[i]) ava[j].push_back(i);
        }
        // for (auto &i : ava[c[n - 1]]) M[1][i] = 1;
        // for (auto [x, y] : M[1]) if (y >= m) b[n - 1] = true;
        // for (int i = n - 2; i >= 0; i--) {
        //     for (auto &j : ava[c[i]]) {
        //         M[0][j] = M[1][(j + 1) % m] + 1;
        //         if (M[0][j] >= m) b[i] = true;
        //     }
        //     M[0].swap(M[1]);
        //     M[0].clear();
        // }
        for (auto &i : ava[c[n - 1]]) val[(n - 1) & 1][i] = 1;
        if (ava[c[n - 1]].size() && m == 1) b[n - 1] = true;
        for (int i = n - 2; i >= 0; i--) {
            int now = (i & 1);
            int pre = (now ^ 1);
            for (auto &j : ava[c[i]]) {
                val[now][j] = val[pre][(j == m - 1 ? 0 : j + 1)] + 1;
                if (val[now][j] >= m) b[i] = true;
            }
            for (auto &j : ava[c[i + 1]]) val[pre][j] = 0;
        }
        b = b << m;
        dp[0] = 0;
        dq.push_back(mp(0, 0));
        FOR(i, 1, n + 1) {
            while (dq.size() && dq.front().sc < i - m) dq.pop_front();
            dp[i] = dq.front().fs + 1;
            if (!b[i]) dp[i] = INF;
            while (dq.size() && dq.back().fs >= dp[i]) dq.pop_back();
            dq.push_back(mp(dp[i], i));
        }
        FOR(i, 0, n + 1) debug(i, dp[i]);
        return (dp[n] >= INF ? -1 : dp[n]);
    }
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    n = N;
    m = M;
    k = K;
    c = C;
    clr = B;
    return miku();
}

Compilation message (stderr)

paint.cpp: In function 'int {anonymous}::miku()':
paint.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 39
      |                    ^~
paint.cpp:69:26: note: in expansion of macro 'debug'
   69 |         FOR(i, 0, n + 1) debug(i, dp[i]);
      |                          ^~~~~

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