Submission #1200810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200810		Braabebo10	벽 칠하기 (APIO20_paint)	C++20	40 / 100	1595 ms	26800 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<vector<ll> > ind(k);
    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]), ind[B[i][j]].push_back(i), ind[B[i][j]].push_back(i + m);
        col.push_back(cur);
        sort(all(col[i]));
    }
    vector<ll> ok(n, 0), vis(n, 0);
    map<ll, ll> cnt;
    ll res = 0;
    auto add = [&](ll x) {
        if (++cnt[x] == m)res++;
    };
    auto del = [&](ll x) {
        if (cnt[x]-- == m)res--;
    };
    for (ll i = 0; i + 1 < m; i++)
        for (ll j: ind[a[i]])
            add(j - i);
    for (ll i = 0, r = m - 1; i + m - 1 < n; i++, r++) {
        for (ll j: ind[a[r]])
            add(j - r);
        ok[i] = res > 0;
        for (ll j: ind[a[i]])
            del(j - i);
    }
    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: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37