oj.uz

Submission #730684

# Submission time Handle Problem Language Result Execution time Memory
730684 2023-04-26T09:11:55 Z t6twotwo Painting Walls (APIO20_paint) C++17
0 / 100
 1500 ms 212 KB 
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 1E6;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<vector<int>> f(K);
    for (int i = 0; i < M; i++) {
        for (int x : B[i]) {
            f[x].push_back(i);
        }
    }
    int good = 0;
    vector<int> cnt(M);
    auto add = [&](int x) {
        for (int y : f[C[x]]) {
            if (++cnt[((y - x) % M + M) % M] == M) {
                good++;
            }
        }
    };
    auto rem = [&](int x) {
        for (int y : f[C[x]]) {
            if (cnt[((y - x) % M + M) % M]-- == M) {
                good--;
            }
        }
    };
    for (int i = 0; i < M; i++) {
        add(i);
    }
    vector<int> b;
    for (int i = M; i <= N; i++) {
        if (good) {
            b.push_back(i - 1);
        }
        if (i == N) {
            break;
        }
        rem(i - M);
        add(i);
    }
    int ans = 0;
    for (int i = -1, j = 0; i < N - 1; ans++) {
        while (j + 1 < b.size() && b[j + 1] <= i + M) {
            j++;
        }
        if (j == b.size() || b[j] > i + M) {
            return -1;
        }
        i = b[j];
    }
    return ans;
}

Compilation message

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while (j + 1 < b.size() && b[j + 1] <= i + M) {
      |                ~~~~~~^~~~~~~~~~
paint.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if (j == b.size() || b[j] > i + M) {
      |             ~~^~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 1583 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 1583 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 1583 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 1583 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 1583 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -