Submission #433178

#	Time	Username	Problem	Language	Result	Execution time	Memory
433178		qwerasdfzxcl	Painting Walls (APIO20_paint)	C++14	100 / 100	1380 ms	14256 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

using namespace std;
typedef long long ll;

int minimumInstructions(
    int N, int M, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B) {

    vector<vector<int>> D(K);
    for (int i=0;i<M;i++){
        for (int j=0;j<(int)B[i].size();j++){
            D[B[i][j]].push_back(i);
        }
    }
    for (int i=0;i<K;i++) sort(D[i].begin(), D[i].end());
    vector<pair<int, int>> v, tmp;
    vector<bool> chk(N);
    for (int i=0;i<N;i++){
        if (D[C[i]].empty()){
            swap(v, tmp); tmp.clear();
            continue;
        }
        if (v.empty()){
            for (auto &x:D[C[i]]) v.emplace_back(x, 1);
            continue;
        }

        int pt1 = 0, pt2 = 0;
        for (auto &p:v){
            if (p.second>=M) chk[i-M] = 1;
            p.first++, p.second++;
        }
        if (v.back().first==M && !D[C[i]][0]){
            tmp.emplace_back(0, v.back().second);
            pt2++;
        }
        while(pt1<(int)v.size() && pt2<(int)D[C[i]].size()){
            if (v[pt1].first==D[C[i]][pt2]){
                tmp.push_back(v[pt1]);
                pt1++, pt2++; continue;
            }
            if (v[pt1].first<D[C[i]][pt2]) pt1++;
            else{
                tmp.emplace_back(D[C[i]][pt2], 1);
                pt2++;
            }
        }
        for (;pt2<(int)D[C[i]].size();pt2++) tmp.emplace_back(D[C[i]][pt2], 1);

        swap(v, tmp);
        tmp.clear();
        /*printf("%d: ", i);
        for (auto &p:v) printf("(%d, %d) ", p.first, p.second);
        printf("\n");*/
    }
    for (auto &p:v) if (p.second>=M) chk[N-M] = 1;

    //for (int i=0;i<N;i++) printf("%d ", (int)chk[i]);
    //printf("\n");
    int prv = 0, nxt = -1, cur = 0, cnt = 0;
    while(prv<N){
        bool flag = 0;
        for (int i=cur;i<=prv;i++) if (chk[i]){
            nxt = i+M;
            flag = 1;
        }
        if (!flag) break;
        cnt++;
        cur = prv+1;
        prv = nxt;
    }
    if (prv<N) return -1;
    return cnt;
}

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