Submission #411772

#	Time	Username	Problem	Language	Result	Execution time	Memory
411772		couplefire	Painting Walls (APIO20_paint)	C++17	0 / 100	1 ms	204 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);
    auto add = [&](int p, int sgn){
        int col = c[p];
        for(auto x : belongs[col]){
            int np = (x+p)%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 = 0;
    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;
}

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