Submission #1198974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198974		Gray	Painting Walls (APIO20_paint)	C++20	28 / 100	1595 ms	8776 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
#define ll int
#define ff first
#define ss second
#define ln "\n"

using namespace std;

vector<set<ll>> cols;
vector<ll> c;
ll n, m, k;
set<ll> ls;

void gen_match(){
    for (ll i=0; i<n-m+1; i++){
        bool pos=0;
        for (ll j=0; j<m; j++){
            bool ipos=1;
            for (ll l=0; l<m; l++){
                if (!cols[(j+l)%m].count(c[i+l])) {ipos=0; break;}
            }
            pos|=ipos;
        }
        if (pos) ls.insert(i);
    }
}


int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    n=N; m=M; k=K;
    c = C; cols.assign(m, set<ll>());
    for (ll i=0; i<m; i++){
        for (ll j=0; j<A[i]; j++) {
            cols[i].insert((ll)(B[i][j]));
        }
    }
    gen_match();
    if (!ls.count(0)) return -1;
    ll cur=0, ep=m-1, cnt=1;
    while (ep<n-1){
        auto iter = ls.upper_bound(ep+1); iter--;
        if (*iter==cur) return -1;
        cur=*iter; cnt++; ep=cur+m-1;
    }
    return cnt;
}

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