Submission #1193492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193492		omsincoconut	Painting Walls (APIO20_paint)	C++17	51 / 100	1595 ms	67408 KiB

paint

/*
We just need to check for each length K segment whether there exist a way to color them or not.
*/

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")

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

using namespace std;

const int INF = (int)1e9;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<int> color_contractor[K];
    for (int i = 0; i < M; i++) {
        for (int j : B[i]) {
            color_contractor[j].push_back(i);
        }
    }

    vector<int> cell[M];

    for (int i = 0; i < N; i++) {
        for (int j : color_contractor[C[i]]) {
            cell[((j-i)%M+M)%M].push_back(i+1);
        }
    }

    bool can[N+1];
    fill(can, can+N+1, false);

    for (int j = 0; j < M; j++) {
        if (cell[j].empty()) continue;
        int l = 0, r = 0;
        for (int i = 0; i+M <= N; i++) {
            while (l < cell[j].size() && cell[j][l] <= i) l++;
            while (r < cell[j].size() && cell[j][r] <= i+M) r++;
            if (r-l == M) can[i] = true;
        }
    }

    int dp[N+1];
    fill(dp, dp+N+1, INF);
    dp[0] = 0;
    deque<pair<int, int>> dt;
    for (int i = 0; i <= N; i++) {
        while (!dt.empty() && i-dt.front().first > M) dt.pop_front();
        if (!dt.empty()) dp[i] = dt.front().second+1;
        if (can[i]) {
            while (!dt.empty() && dt.back().second >= dp[i]) dt.pop_back();
            dt.emplace_back(i, dp[i]);
        }
    }

    return (dp[N] >= INF ? -1 : dp[N]);
}

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