제출 #1219231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219231		Mans21	Painting Walls (APIO20_paint)	C++20	100 / 100	282 ms	16836 KiB

paint

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

using namespace std;

const int maxn = 100'000 + 12;

vector<int> g[maxn], u[maxn];
int Cur[maxn], cnt[maxn];
bool is[maxn];

int minimumInstructions(
    int n, int m, int k, vector<int> c, vector<int> A, vector<vector<int>> B) {

    for(int i = 0; i < m; i++) {
        sort(B[i].begin(), B[i].end());
        for(int x : B[i]) {
            g[x].push_back(i);
        }
    }

    for(int j = 0; j < n; j++) {
        u[max(0, j - m + 1)].push_back(j);
        for(int i : g[c[j]]) {
            int val = (i - j) % m;
            if(val < 0) val += m;
            val++;
        }
    }

    for(int i = 0; i < n; i++) {
        for(int y : u[i]) {
            for(int x : g[c[y]]) {
                int val = (x - y) % m;
                if(val < 0) val += m;
                cnt[Cur[val]]--;
                Cur[val]++;
                cnt[Cur[val]]++;
            }
        }
        is[i] = (cnt[m] > 0);
        for(int x : g[c[i]]) {
            int val = (x - i) % m;
            if(val < 0) val += m;
            cnt[Cur[val]]--;
            Cur[val]--;
            cnt[Cur[val]]++;
        }
    }

    int ans = 0, last = -1e9, cur = -1e9;
    for(int i = 0; i < n; i++) {
        if(is[i]) last = i;
        if(i - cur >= m) {
            if(i - last >= m) {
                return -1;
            }
            cur = last;
            ans++;
        }
    }
    return ans;
}

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