Submission #1253580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253580		cpismylifeOwO	Painting Walls (APIO20_paint)	C++20	100 / 100	360 ms	321648 KiB

paint

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

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

#ifdef cpismylifeOwO
int ni, mi, ki;
vector<int> ci;
vector<int> aii;
vector<vector<int>> bii;

void Inp()
{
    cin >> ni >> mi >> ki;
    ci.resize(ni);
    for (int x = 0; x < ni; x++)
    {
        cin >> ci[x];
    }
    aii.resize(mi);
    bii.resize(mi);
    for (int x = 0; x < mi; x++)
    {
        cin >> aii[x];
        for (int y = 1; y <= aii[x]; y++)
        {
            int p;
            cin >> p;
            bii[x].push_back(p);
        }
    }
}
#endif // cpismylifeOwO

int n, m, k;
int arr[MaxN];
vector<int> now[MaxN];
vector<int> mark[MaxN];
vector<int> F[MaxN];
bool good[MaxN];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B)
{
    n = N;
    m = M;
    k = K;
    for (int x = 1; x <= n; x++)
    {
        arr[x] = C[x - 1] + 1;
    }
    for (int x = 1; x <= m; x++)
    {
        now[x].resize(A[x - 1] + 5);
        for (int y : B[x - 1])
        {
            now[x].push_back(y + 1);
            mark[y + 1].push_back(x);
        }
    }
    for (int x = 1; x <= k; x++)
    {
        if (!mark[x].empty())
        {
            mark[x].push_back(mark[x][0] + m);
        }
    }
    if (mark[arr[n]].empty())
    {
        return -1;
    }
    F[n].resize(mark[arr[n]].size() - 1);
    for (int x = 0; x < (int)mark[arr[n]].size() - 1; x++)
    {
        F[n][x] = 1;
    }
    good[n] = (m == 1);
    for (int x = n - 1; x > 0; x--)
    {
        if (mark[arr[x]].empty())
        {
            return -1;
        }
        F[x].resize(mark[arr[x]].size() - 1);
        good[x] = false;
        int z = 0;
        for (int y = 0; y < (int)F[x].size(); y++)
        {
            while (z < (int)mark[arr[x + 1]].size() && mark[arr[x]][y] >= mark[arr[x + 1]][z])
            {
                z++;
            }
            if (z < (int)mark[arr[x + 1]].size() && mark[arr[x]][y] + 1 == mark[arr[x + 1]][z])
            {
                F[x][y] = F[x + 1][z % (int)F[x + 1].size()] + 1;
            }
            else
            {
                F[x][y] = 1;
            }
            good[x] |= (F[x][y] >= m);
        }
    }
    if (!good[1])
    {
        return -1;
    }
    priority_queue<int> pq;
    pq.push(1);
    int curmx = 1, res = 0;
    while (!pq.empty())
    {
        int p = pq.top();
        res++;
        pq.pop();
        for (int x = curmx + 1; x <= p + m; x++)
        {
            if (good[x])
            {
                pq.push(x);
            }
        }
        curmx = p + m;
        if (curmx > n)
        {
            return res;
        }
    }
    return -1;
}

#ifdef cpismylifeOwO
void Exc()
{
    cout << minimumInstructions(ni, mi, ki, ci, aii, bii);
}

int main()
{
    freopen("PAINT.INP", "r", stdin);
    //freopen("PAINT.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}
#endif // cpismylifeOwO

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