oj.uz

Submission #788653

# Submission time Handle Problem Language Result Execution time Memory
788653 2023-07-20T12:42:59 Z mindiyak Painting Walls (APIO20_paint) C++14
0 / 100
 38 ms 55944 KB 
#include "paint.h"

#include <vector>
#include <unordered_set>
#include <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>());

  bool case1 = true;
  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]);
      if(colors[B[i][j]].size() > 1){
        case1 = false;
      }
    }
  }

  bool possible = true;
  set<pair<int,int>> minimumele;
  vector<set<pair<int,int>>::iterator> remove_arr;
  
  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){
      if(i==0){
        dp[(M-1+i)] = 1;
      }else{
        dp[(M-1+i)] = dp[i-1]+1;
      }
      int minimum = 1000000;
      auto l=minimumele.begin();

      while(l!=minimumele.end()){
        auto minimum_pair = *l;
        if(minimum_pair.second < i){
          remove_arr.push_back(l);
        }else{
          minimum = minimum_pair.first;
          break;
        }
        l++;
      }
      // cout << i << " " << minimum  << " " << remove_arr.size() << endl;
      for(int n=0;n<(int)remove_arr.size();n++){
          minimumele.erase(remove_arr[n]);
      }
      dp[(M-1+i)] = min(dp[(M-1+i)],minimum+1);
      minimumele.insert({dp[(M-1+i)], M-1+i});
      // cout << " pos-" << (M-1+i) << " dp[M-1]-" << dp[(M-1+i)] << endl;
    }else{
      if(case1){
        return -1;
      }
    }
    // 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 15 ms 27732 KB Output is correct
2 Correct 15 ms 27652 KB Output is correct
3 Correct 15 ms 27696 KB Output is correct
4 Correct 17 ms 27696 KB Output is correct
5 Correct 16 ms 27684 KB Output is correct
6 Correct 15 ms 27716 KB Output is correct
7 Runtime error 38 ms 55944 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27732 KB Output is correct
2 Correct 15 ms 27652 KB Output is correct
3 Correct 15 ms 27696 KB Output is correct
4 Correct 17 ms 27696 KB Output is correct
5 Correct 16 ms 27684 KB Output is correct
6 Correct 15 ms 27716 KB Output is correct
7 Runtime error 38 ms 55944 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27732 KB Output is correct
2 Correct 15 ms 27652 KB Output is correct
3 Correct 15 ms 27696 KB Output is correct
4 Correct 17 ms 27696 KB Output is correct
5 Correct 16 ms 27684 KB Output is correct
6 Correct 15 ms 27716 KB Output is correct
7 Runtime error 38 ms 55944 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27732 KB Output is correct
2 Correct 15 ms 27652 KB Output is correct
3 Correct 15 ms 27696 KB Output is correct
4 Correct 17 ms 27696 KB Output is correct
5 Correct 16 ms 27684 KB Output is correct
6 Correct 15 ms 27716 KB Output is correct
7 Runtime error 38 ms 55944 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27732 KB Output is correct
2 Correct 15 ms 27652 KB Output is correct
3 Correct 15 ms 27696 KB Output is correct
4 Correct 17 ms 27696 KB Output is correct
5 Correct 16 ms 27684 KB Output is correct
6 Correct 15 ms 27716 KB Output is correct
7 Runtime error 38 ms 55944 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -