Submission #560808

#	Time	Username	Problem	Language	Result	Execution time	Memory
560808		nghiass001	Painting Walls (APIO20_paint)	C++17	0 / 100	12 ms	12088 KiB

paint

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)

using namespace std;
using namespace __gnu_pbds;

template <class key, class value>
using ordered_map = tree<key, value, less<key>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 100005, maxM = 50005, logM = 16, maxK = 100005, INF = 0x3c3c3c3c;
int kmp[maxM], kmp2[maxM], prefix[N], suffix[N], ans[N];
int p[maxM][logM];
vector<int> Q[maxK];
ordered_map<int, int> M[maxM], M_next[maxM];

int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B) {
    C.insert(C.begin(), -1);
    A.insert(A.begin(), 0);
    B.insert(B.begin(), vector<int>());

    FOR(i, 1, m) {
        for(int v : B[i]) {
            Q[v].push_back(i);
            M[i][v] = 1;
        }
    }

    FOR(i, 1, k) {
        for(int u : Q[i])
            for(int v : Q[i]) M_next[u][v] = 1;
    }

    /// all about kmp
    kmp[0] = -1;
    FOR(i, 2, m) {
        for(int j = kmp[i - 1]; j != -1; j = kmp[j]) {
            if (M_next[i][j + 1]) {
                kmp[i] = j + 1;
                break;
            }
        }
    }
    prefix[0] = 0;
    FOR(i, 1, n) {
        for(int j = prefix[i - 1]; j != -1; j = kmp[j]) {
            if (M[j + 1][C[i]]) {
                prefix[i] = j + 1;
                break;
            }
        }
    }

    kmp2[m + 1] = m + 2;
    kmp2[m] = m + 1;
    FORD(i, m - 1, 1) {
        kmp2[i] = m + 1;
        for(int j = kmp2[i + 1]; j != m + 2; j = kmp2[j]) {
            if (M_next[i][j - 1]) {
                kmp2[i] = j - 1;
                break;
            }
        }
    }
    suffix[n + 1] = m + 1;
    FORD(i, n, 1) {
        suffix[i] = m + 1;
        for(int j = suffix[i + 1]; j != m + 2; j = kmp2[j]) {
            if (M[j - 1][C[i]]) {
                suffix[i] = j - 1;
                break;
            }
        }
    }

    /// build
    FOR(i, 1, m) p[i][0] = kmp[i];
    REP(j, 1, logM) FOR(i, 1, m) p[i][j] = p[p[i][j - 1]][j - 1];
    /// solve
    FOR(i, 1, m - 1) ans[i] = INF;

    FOR(i, m, n) {
        ans[i] = INF;
        int vx = prefix[i];
        int hope = suffix[i - m + 1] - 1;
        REPD(j, logM, 0) if (p[vx][j] >= hope) vx = p[vx][j];
        if (vx == hope) {
            ans[i] = ans[i - m] + 1;
        }
        FORD(j, i - 1, i - m) {
            if (ans[j] > ans[i]) ans[j] = ans[i];
            else break;
        }
    }

    if (ans[n] == INF) ans[n] = -1;
    return ans[n];
}

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