oj.uz

Submission #877549

# Submission time Handle Problem Language Result Execution time Memory
877549 2023-11-23T10:12:19 Z boris_mihov Painting Walls (APIO20_paint) C++17
0 / 100
 2 ms 8540 KB 
#include "paint.h"
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n, m, k;
int a[MAXN];
int zeroLen[MAXN];
int lastLen[MAXN];
std::vector <int> canUse[MAXN];
std::unordered_set <int> canUseSet[MAXN];
bool isGood[MAXN];

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 = 1 ; i <= n ; ++i)
    {
        a[i] = C[i - 1] + 1;
    }

    for (int i = 0 ; i < m ; ++i)
    {
        for (int j = 0 ; j < A[i] ; ++j)
        {
            canUse[B[i][j] + 1].push_back(i + 1);
            canUseSet[B[i][j] + 1].insert(i + 1);
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = i ; j <= std::min(i + m - 1, n) ; ++j)
        {
            if (!canUseSet[a[j]].count(j - i + 1))
            {
                break;
            }

            zeroLen[i]++;
        }

        for (int j = i ; j >= std::min(i - m + 1, 1) ; --j)
        {
            if (!canUseSet[a[j]].count(m - (i - j)))
            {
                break;
            }

            lastLen[i]++;
        }
    }

    for (int i = 1 ; i + m - 1 <= n ; ++i)
    {
        for (const int &c : canUse[a[i]])
        {
            if (lastLen[i + m - c] >= m - c + 1 && zeroLen[i + m - c + 1] >= c - 1)
            {
                isGood[i] = true;
                break;
            }
        }
    }

    if (!isGood[1])
    {
        return -1;
    }

    int ptr = 1;
    int ans = 0;
    int dest = m;
    assert(isGood[1]);

    while (ptr <= n)
    {
        if (dest == 0) return -1;
        int newDest = 0;
        while (ptr <= dest)
        {
            if (isGood[ptr]) newDest = std::max(newDest, ptr + m);
            ptr++;
        }

        dest = newDest;
        ans++;
    }

    return ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -