Submission #788653

#	Time	Username	Problem	Language	Result	Execution time	Memory
788653		mindiyak	Painting Walls (APIO20_paint)	C++14	0 / 100	38 ms	55944 KiB

paint

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37