제출 #341788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341788		phathnv	벽 칠하기 (APIO20_paint)	C++11	100 / 100	541 ms	15212 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

#define X first
#define Y second
#define mp make_pair

using namespace std;

typedef pair<int, int> ii;

const int maxN = 100000;
const int maxK = 100000;
const int maxM = 50000;
const int maxfK = 632;

int n, m, k, c[maxN];
vector <int> hasColor[maxK];

bool mark[maxN];
int nF[2];
ii f[2][maxfK], g[maxM];

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    n = N;
    m = M;
    k = K;
    for(int i = 0; i < n; i++)
        c[i] = C[i];
    for(int i = 0; i < m; i++)
        for(int col : B[i])
            hasColor[col].push_back(i);

    for(int i = 0; i < n; i++){
        int id = i & 1;
        for(int j = 0; j < nF[id ^ 1]; j++)
            g[f[id ^ 1][j].X] = mp(i, f[id ^ 1][j].Y);
        nF[id] = 0;

        for(int x : hasColor[c[i]]){
            int pre = (x + m - 1) % m;
            if (g[pre].X == i)
                f[id][nF[id]++] = mp(x, g[pre].Y + 1);
            else
                f[id][nF[id]++] = mp(x, 1);

            if (f[id][nF[id] - 1].Y >= m)
                mark[i - m + 1] = 1;
        }
    }

    int cur = -1, best = -1, res = 0;
    for(int i = 0; i < n; i++){
        if (mark[i])
            best = i + m - 1;
        if (cur < i){
            res++;
            cur = best;
        }
        if (cur < i)
            return -1;
    }

    return res;
}

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