oj.uz

Submission #788601

# Submission time Handle Problem Language Result Execution time Memory
788601 2023-07-20T11:55:42 Z mindiyak Painting Walls (APIO20_paint) C++14
0 / 100
 16 ms 27732 KB 
#include "paint.h"

#include <vector>
#include <unordered_set>
// #include <iostream>

using namespace std;

vector<int> dp(1000000,1e9);
vector<vector<int>> colors(1000000,vector<int>()); 

int minimumInstructions(int N, int M, int K, std::vector<int> C,std::vector<int> A, std::vector<std::vector<int>> B) {
  vector<unordered_set<int>> contrcatorColor(M,unordered_set<int>());

  for(int i=0;i<M;i++){
    for(int j=0;j<A[i];j++){
      colors[B[i][j]].push_back(i);
      contrcatorColor[i].insert(B[i][j]);
    }
  }

  bool possible = true;
  for(int i=0;i<=(N-M);i++){
    // cout << "start pos is " << i << endl;
    bool coloured = false;
    for(int j=0;j<(int)colors[C[i]].size();j++){
      int contractorStart = colors[C[i]][j];
      possible = true;
      // cout << "contractor start " << contractorStart << endl;
      for(int k=0;k<M;k++){
        // cout << (contractorStart+k)%M << " contractor " << C[i+k] << " color " << contrcatorColor[(contractorStart+k)%M].count(C[i+k]) << endl;
        if(contrcatorColor[(contractorStart+k)%M].count(C[i+k]) == 0){
          possible = false;
          break;
        }
      }
      if(possible){
        // cout << "possible to paint " << i << " start from " << contractorStart << endl; 
        coloured = true;
        break;
      }
    }
    
    if(coloured){
      // cout << "i-" << i;
      if(i>0 and dp[i-1]!= -1){
        // cout << " dp[i-1]" << dp[i-1]; 
        dp[(M-1+i)] = dp[i-1]+1;
      }else{
        // cout << "start ";
        dp[(M-1+i)] = 1;
      }
      dp[(M-1+i)] = min(dp[(M-1+i)],dp[i]+1);
      dp[(M-1+i)] = min(dp[(M-1+i)],dp[i+1]+1);
      // cout << " pos-" << (M-1+i) << " dp[M-1]-" << dp[(M-1+i)] << endl;
    }
    // cout << endl;
  }

  // for(int i=0;i<N;i++){
  //   cout << dp[i] << " ";
  // }cout << endl;

  if(dp[N-1] >= 1e9){
    return -1;
  }
  return dp[N-1];
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 13 ms 27632 KB Output is correct
3 Correct 15 ms 27604 KB Output is correct
4 Correct 14 ms 27592 KB Output is correct
5 Correct 14 ms 27644 KB Output is correct
6 Correct 14 ms 27604 KB Output is correct
7 Correct 15 ms 27604 KB Output is correct
8 Correct 16 ms 27636 KB Output is correct
9 Correct 14 ms 27708 KB Output is correct
10 Correct 14 ms 27604 KB Output is correct
11 Correct 15 ms 27632 KB Output is correct
12 Correct 14 ms 27604 KB Output is correct
13 Incorrect 15 ms 27732 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 13 ms 27632 KB Output is correct
3 Correct 15 ms 27604 KB Output is correct
4 Correct 14 ms 27592 KB Output is correct
5 Correct 14 ms 27644 KB Output is correct
6 Correct 14 ms 27604 KB Output is correct
7 Correct 15 ms 27604 KB Output is correct
8 Correct 16 ms 27636 KB Output is correct
9 Correct 14 ms 27708 KB Output is correct
10 Correct 14 ms 27604 KB Output is correct
11 Correct 15 ms 27632 KB Output is correct
12 Correct 14 ms 27604 KB Output is correct
13 Incorrect 15 ms 27732 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 13 ms 27632 KB Output is correct
3 Correct 15 ms 27604 KB Output is correct
4 Correct 14 ms 27592 KB Output is correct
5 Correct 14 ms 27644 KB Output is correct
6 Correct 14 ms 27604 KB Output is correct
7 Correct 15 ms 27604 KB Output is correct
8 Correct 16 ms 27636 KB Output is correct
9 Correct 14 ms 27708 KB Output is correct
10 Correct 14 ms 27604 KB Output is correct
11 Correct 15 ms 27632 KB Output is correct
12 Correct 14 ms 27604 KB Output is correct
13 Incorrect 15 ms 27732 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 13 ms 27632 KB Output is correct
3 Correct 15 ms 27604 KB Output is correct
4 Correct 14 ms 27592 KB Output is correct
5 Correct 14 ms 27644 KB Output is correct
6 Correct 14 ms 27604 KB Output is correct
7 Correct 15 ms 27604 KB Output is correct
8 Correct 16 ms 27636 KB Output is correct
9 Correct 14 ms 27708 KB Output is correct
10 Correct 14 ms 27604 KB Output is correct
11 Correct 15 ms 27632 KB Output is correct
12 Correct 14 ms 27604 KB Output is correct
13 Incorrect 15 ms 27732 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 13 ms 27632 KB Output is correct
3 Correct 15 ms 27604 KB Output is correct
4 Correct 14 ms 27592 KB Output is correct
5 Correct 14 ms 27644 KB Output is correct
6 Correct 14 ms 27604 KB Output is correct
7 Correct 15 ms 27604 KB Output is correct
8 Correct 16 ms 27636 KB Output is correct
9 Correct 14 ms 27708 KB Output is correct
10 Correct 14 ms 27604 KB Output is correct
11 Correct 15 ms 27632 KB Output is correct
12 Correct 14 ms 27604 KB Output is correct
13 Incorrect 15 ms 27732 KB Output isn't correct
14 Halted 0 ms 0 KB -