Submission #966520

#	Time	Username	Problem	Language	Result	Execution time	Memory
966520		gaga999	Painting Walls (APIO20_paint)	C++17	0 / 100	5 ms	8284 KiB

paint

#include <cstdio>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100005;
vector<int> d[maxn];
int n, m, k, vis[2][maxn], dp[2][maxn], ok[maxn];
struct node
{
    int l, r;
} s[maxn];
bool cmp(node a, node b)
{
    return a.l < b.l;
}
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 i = 1; i <= n; i++)
        C[i - 1]++;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j < A[i - 1]; j++)
            B[i - 1][j]++;
    }
    for (int i = 1; i < maxn; i++)
        d[i].push_back(0);
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j < A[i - 1]; j++)
            d[B[i - 1][j]][0]++, d[B[i - 1][j]].push_back(i);
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j <= d[C[i - 1]][0]; j++)
        {
            if (vis[(i + 1) & 1][d[C[i - 1]][j] % m + 1] == i + 1)
                dp[i & 1][d[C[i - 1]][j]] = dp[(i + 1) & 1][d[C[i - 1]][j] % m + 1] + 1;
            else
                dp[i & 1][d[C[i - 1]][j]] = 1;
            vis[i & 1][d[C[i - 1]][j]] = i;
            if (dp[i & 1][d[C[i - 1]][j]] >= m)
                ok[i] = 1;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n - m + 1; i++)
    {
        if (ok[i])
        {
            cnt++;
            s[cnt].l = i;
            s[cnt].r = i + m - 1;
        }
    }
    if (!ok[1] || !ok[n - m + 1])
        return -1;
    else if (n == m)
        return 1;
    int l = 1, r = m + 1, ans = 1;
    for (int i = 1; i <= n; i++)
    {
        while (i < r)
            if (ok[++i])
                l = i;
        if (l == r - m)
            return -1;
        ans++, r = l + m;
        if (r == n + 1)
            return ans;
    }
    return -1;
}

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