Submission #1165679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165679		SmuggingSpun	Painting Walls (APIO20_paint)	C++20	100 / 100	258 ms	14784 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
const int INF = 1e9;
template<class T>void minimize(T& a, T b){
    if(a > b){
        a = b;
    }
}
template<class T>void maximize(T& a, T b){
    if(a < b){
        a = b;
    }
}
int minimumInstructions(int n, int m, int k, vector<int>c, vector<int>a, vector<vector<int>>b){
    bool is_sub1 = true;
    auto pre_check = [&] (){
        vector<int>cnt(k, 0);
        for(int i = 0; i < m; i++){
            for(int& j : b[i]){
                if(cnt[j]++ == 1){
                    is_sub1 = false;
                    return;
                }
            }
        }
    };
    pre_check();
    if(is_sub1){
        vector<int>to(k, -2);
        for(int i = 0; i < m; i++){
            for(int& j : b[i]){
                to[j] = i;
            }
        }
        int cnt = 1, ans = 0, pre = to[c[0]];
        for(int i = 1; i < n; i++, cnt++){
            if(cnt == m){
                cnt = 0;
                if((pre = to[c[i]]) == -2){
                    return -1;
                }
                ans++;
            }
            else if(to[c[i]] != (pre = (pre + 1) % m)){
                return -1;
            }
        }
        return ans + 1;
    }
    if(n <= 20000 && m <= 2000){
        vector<vector<int>>p(k);
        for(int i = 0; i < n; i++){
            p[c[i]].emplace_back(i);
        }
        vector<vector<bool>>can(m, vector<bool>(n, false));
        for(int i = 0; i < m; i++){
            for(int& j : b[i]){
                for(int& k : p[j]){
                    can[i][k] = true;
                }
            }
        }
        vector<bool>paint(n, false);
        for(int i = 0; i + m <= n; i++){
            for(int j = 0; j < m; j++){
                bool flag = true;
                for(int k = 0; k < m; k++){
                    if(!can[(j + k) % m][i + k]){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    paint[i] = true;
                    break;
                }
            }
        }
        vector<int>dp(n + 1, INF);
        dp[n] = 0;
        for(int i = n - 1; i > -1; dp[i--]++){
            for(int j = min(i, n - m); j >= max(0, i - m + 1); j--){
                if(paint[j]){
                    for(int k = i; k < j + m; k++){
                        minimize(dp[i], dp[k + 1]);
                    }
                    break;
                }
            }
        }
        return dp[0] >= INF ? -1 : dp[0];
    }
    vector<vector<int>>ins(k);
    for(int i = 0; i < m; i++){
        for(int& j : b[i]){
            ins[j].emplace_back(i);
        }
    }
    vector<int>f(n, 0);
    vector<pair<int, int>>state;
    for(int& i : ins[c[0]]){
        state.emplace_back(i, 1);
    }
    f[0] = int(!state.empty());
    for(int i = 1; i < n; i++){
        vector<pair<int, int>>nxt_state;
        for(int& j : ins[c[i]]){
            nxt_state.emplace_back(j, 1);
        }
        if(!nxt_state.empty()){
            nxt_state.emplace_back(nxt_state[0]);
            nxt_state.back().first += m;
            int ptr = 0;
            for(auto& [p, v] : state){
                while(nxt_state[ptr].first <= p){
                    ptr++;
                }
                if(nxt_state[ptr].first == p + 1){
                    nxt_state[ptr].second = v + 1;
                }
            }
            maximize(nxt_state[0].second, nxt_state.back().second);
            nxt_state.pop_back();
        }
        swap(state, nxt_state);
        for(auto& [foo, v] : state){
            maximize(f[i], v);
        }
    }
    vector<bool>paint(n, false);
    for(int i = 0; i < n; i++){
        if(f[i] >= m){
            paint[i - m + 1] = true;
        }
    }
    vector<int>left(n, -1);
    if(paint[0]){
        left[0] = 0;
    }
    for(int i = 1; i < n; i++){
        left[i] = (paint[i] ? i : left[i - 1]);
    }
    vector<int>st((n + 1) << 2, INF);
    function<void(int, int)>update;
    update = [&] (int p, int x){
        int id = 1, l = 0, r = n;
        while(l < r){
            minimize(st[id], x);
            int m = (l + r) >> 1;
            id <<= 1;
            if(m < p){
                l = m + 1;
                id |= 1;
            }
            else{
                r = m;
            }
        }
        st[id] = x;
    };
    function<int(int, int, int, int, int)>get;
    get = [&] (int id, int l, int r, int u, int v){
        if(l > v || r < u){
            return INF;
        }
        if(u <= l && v >= r){
            return st[id];
        }
        int m = (l + r) >> 1;
        return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
    };
    update(n, 0);
    for(int i = n - 1; i > -1; i--){
        if(left[i] >= max(0, i - m + 1)){
            update(i, get(1, 0, n, i + 1, left[i] + m) + 1);
        }
    }
    int ans = get(1, 0, n, 0, 0);
    return ans >= INF ? -1 : ans;
}

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