Submission #411775

#	Time	Username	Problem	Language	Result	Execution time	Memory
411775		couplefire	Painting Walls (APIO20_paint)	C++17	100 / 100	1362 ms	15228 KiB

paint

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

const int N = 1e5+5;
vector<int> good;
int ans[N/2], cnt[N/2];
vector<int> belongs[N];
vector<int> _c;
int _m;

void add(int p, int sgn){
    int col = _c[p];
    for(int x : belongs[col]){
        int np = (x-p%_m+_m)%_m;
        cnt[ans[np]]--;
        ans[np] += sgn;
        cnt[ans[np]]++;
    }
}

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b){
    _c = c; _m = m;
    for(int i = 0; i<m; i++)
        for(auto col : b[i])
            belongs[col].push_back(i);
    cnt[0] = m;
    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(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: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37