oj.uz

Submission #979738

# Submission time Handle Problem Language Result Execution time Memory
979738 2024-05-11T10:38:42 Z vjudge1 Painting Walls (APIO20_paint) C++17
0 / 100
 2 ms 2652 KB 
#include <bits/stdc++.h>
#include "paint.h"

using namespace std;
using ll = long long;

const int N1 = 20200;
const int M1 = 2020;

int n, m;

const int N = 100100;
const int K = 100100;

bool able[N] = {};
int to[N] = {};

vector<int> inst[K];

vector<vector<int>> f;

int minimumInstructions(
    int N, int M, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B) {
    n = N,
    m = M;

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

    auto get = [&](int i, int j) -> int {
        if (i == n) return 0;
        int x = lower_bound(inst[C[i]].begin(), inst[C[i]].end(), j) 
                - inst[C[i]].begin();
            
        if (x != (int)inst[C[i]].size() && inst[C[i]][x] == j)
            return f[i][x];
        return 0;
    };

    f.resize(n + 1);

    for (int i = n - 1; i >= 0; i--) {
        f[i].resize((int)inst[C[i]].size() + 1);

        for (int j = 0; j < (int)f[i].size(); j++) {
            f[i][j] = 1 + get(i + 1, (inst[C[i]][j] + 1) % m);
        }
    }
    for (int i = 0; i <= n - m; i++) {
        for (int c : f[i])
            if (c >= m)
                able[i] = true;
    }
    
    {
        if (!able[0]) return -1;
        
        int nxt = 0, w = 0;
        for (int i = 0; i < n; i++) {
            if (able[i]) 
                nxt = (i + m);
            to[i] = max(nxt, i);
        }
    }

    int res = 1e9;

    int x = 0, ans = 0;
    while (x < n && x != to[x]) {
        ans++;
        x = to[x];
    }
    if (x == n) return ans;
    return -1;
}

Compilation message

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:64:22: warning: unused variable 'w' [-Wunused-variable]
   64 |         int nxt = 0, w = 0;
      |                      ^
paint.cpp:72:9: warning: unused variable 'res' [-Wunused-variable]
   72 |     int res = 1e9;
      |         ^~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 37.0

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