Submission #1200768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200768		Braabebo10	Painting Walls (APIO20_paint)	C++20	28 / 100	1593 ms	12340 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int> > B) {
    ll n = N, m = M, k = K;
    vector<ll> a, sz;
    vector<vector<ll> > col;
    set<ll> s;
    vector<bitset<4001>>bits(n);
    for (ll i = 0; i < n; i++)a.push_back(C[i]), s.insert(C[i]);
    for (ll i = 0; i < m; i++) {
        sz.push_back(A[i]);
        vector<ll> cur;
        for (ll j = 0; j < sz[i]; j++)
            cur.push_back(B[i][j]);
        col.push_back(cur);
    }
    for (ll c: s) {
        bitset<4001> cur = 0;
        for (ll i = 0; i < 2 * m; i++)
            cur[i] = (find(all(col[i % m]), c) != col[i % m].end());
        for (ll i = 0; i < n; i++)
            if (c == a[i])
                bits[i] = cur;
    }
    vector<ll> ok(n, 0), vis(n, 0);
    for (ll i = 0; i + m - 1 < n; i++) {
        bitset<4001> cur;
        cur.set();
        for (ll j = i, len = 0; j < n and len < m; len++, j++)
            cur &= (bits[j] >> len);
        ok[i] = cur.count() > 0;
    }
    ll u = 0, steps = 0;
    while (u < n) {
        if (vis[u] >= 3)return -1;
        vis[u]++;
        steps++;
        if (ok[u])u += m;
        else {
            if (u)u--, steps--;
            else return -1;
        }
    }
    return steps;
}

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