Submission #411773

#	Time	Username	Problem	Language	Result	Execution time	Memory
411773		couplefire	Painting Walls (APIO20_paint)	C++17	63 / 100	1578 ms	14508 KiB

paint

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

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b){
    vector<int> good;
    vector<int> ans(m, 0), cnt(m+1, 0);
    vector<vector<int>> belongs(k);
    for(int i = 0; i<m; i++)
        for(auto col : b[i])
            belongs[col].push_back(i);
    cnt[0] = m;
    auto add = [&](int p, int sgn){
        int col = c[p];
        for(auto x : belongs[col]){
            int np = (x-p%m+m)%m;
            cnt[ans[np]]--;
            ans[np] += sgn;
            cnt[ans[np]]++;
        }
    };
    for(int i = 0; i<m; i++) add(i, 1);
    if(cnt[m]) good.push_back(0);
    for(int i = 1; i<=n-m; i++){
        add(i-1, -1), add(i+m-1, 1);
        if(cnt[m]) good.push_back(i);
    }
    if(!good.size() || good.front() != 0 || good.back() != n-m)
        return -1;
    int pg = 0, res = 1;
    // for(auto x : good) cout << x << " ";
    // cout << "\n";
    for(int i = 1; i<(int)good.size(); i++){
        if(good[i]-good[pg] > m) return -1;
        if(i == (int)good.size()-1 || good[i+1]-good[pg] > m)
            res++, pg = i;
    }
    return res;
}

// int main(){
//     cout << minimumInstructions(8, 3, 5, {3, 3, 1, 3, 4, 4, 2, 2}, {3, 2, 2}, {{0, 1, 2}, {2, 3}, {3, 4}}) << endl;
// }

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