oj.uz

Submission #982793

# Submission time Handle Problem Language Result Execution time Memory
982793 2024-05-14T18:10:02 Z Marcus Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 348 KB 
#include "paint.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
const int INF = 1e5+1;


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;
    vector<int> color(k, -1);
    for (int i=0; i<m; i++) {color[B[i][0]] = i;}
    for (auto u: color) {if (u == -1) return -1;}
    vector<int> cHat(n);
    for (int i=0; i<n; i++) {cHat[i] = color[C[i]];}
    vector<int> right(n);
    for (int i=n-1; i>=0; i--)
    {
        if (i == n-1 || cHat[i+1] != (cHat[i]+1)%m) right[i] = i;
        else right[i] = right[i+1];
    }
    vector<bool> p(n);
    for (int i=0; i<n; i++)
    {
        p[i] = (right[i] - i + 1 >= m);
    }
    //for (auto &u: B) {for (auto &v: u) {cout<<v<<" ";} cout<<'\n';}
    //for (auto u: p) {cout<<u<<" ";} cout<<'\n';

    vector<int> left(n);
    if (p[0]) left[0] = 0;
    else left[0] = -INF;
    for (int i=1; i<n; i++)
    {
      if (p[i]) left[i] = i;
      else left[i] = left[i-1];
    }
    //for (auto u: left) {cout<<u<<" ";} cout<<"\n";

    vector<int> g(n);
    for (int i=n-1; i>=0; i--)
    {
      //cout<<left[i]+m-1<<"\n";
      if (i - left[i] >= m) {g[i] = INF;}
      else if (left[i] != -INF && left[i]+m >= n) {g[i] = 1;}
      else if (left[i] != -INF && left[i]+m < n) {g[i] = 1 + g[left[i]+m];}
    }
    //for (auto u: g) {cout<<u<<" ";} cout<<"\n";


    return ((g[0] >= INF) ? -1 : g[0]);
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 37.0

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