提出 #27574012

---

ソースコード 拡げる

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, K;
    std::cin >> N >> K;
    
    std::vector<int> i(K);
    for (int k = 0; k < K; k++) {
        std::cin >> i[k];
        i[k]--;
    }
    
    std::vector<int> last(K), cur(N, -1); 
    for (int k = 0; k < K; k++) {
        last[k] = cur[i[k]];
        cur[i[k]] = k;
    }
    
    std::vector<int> f(K + 1);
    int cnt = 0, mx = -1;
    for (int k = 0; k < K; k++) {
        mx = std::max(mx, last[k]);
        if (last[k] == -1) {
            cnt++;
        }
        f[k + 1] = (mx >= k + 1 - cnt || f[k + 1 - cnt] == -1) ? -1 : 1 + f[k + 1 - cnt];
    }
    
    int c = -1, len = -1;
    for (int k = mx + 1; k <= K; k++) {
        if (f[k] >= 0 && (c == -1 || c >= f[k])) {
            c = f[k];
            len = k;
        }
    }
    
    if (c == -1) {
        std::cout << "-1\n";
        return 0;
    }
    
    std::vector<int> A(N, c + 1);
    for (int k = 0; k < len; k++) {
        A[i[k]]--;
    }
    for (int i = 0; i < N; i++) {
        std::cout << A[i] << " \n"[i == N - 1];
    }
    
    return 0;
}

提出情報

ジャッジ結果