oj.uz

Submission #789409

# Submission time Handle Problem Language Result Execution time Memory
789409 2023-07-21T10:56:23 Z mindiyak Painting Walls (APIO20_paint) C++14
0 / 100
 1500 ms 31628 KB 
#include "paint.h"

#include <vector>
#include <unordered_set>
#include <set>
#include <iostream>

using namespace std;

vector<int> dp(1000000,1e9); 
vector<int> possibility(1000000,0); 
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;

  
  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){
      possibility[i+M-1] = 1;
    }
    // cout << endl;
  }

  int ans = 0;
  set<pair<int,int>> values;

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

  for(int i=M-1;i<N;i++){
    pair<int,int> a = *values.begin();
    // for(auto k:values){
    //   cout << i << " " << k.first << " " << k.second << endl;
    // }cout << endl;
    if(a.second < (i-M)){
      values.erase(a);
      i--;
      continue;
    }
    if(possibility[i]){
      values.insert({a.first+1,i});
    }

    if(i == N-1){
      if(possibility[i]){
        return a.first+1;
      }else{
        return -1;
      }
    }
  }

  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:17:8: warning: variable 'case1' set but not used [-Wunused-but-set-variable]
   17 |   bool case1 = true;
      |        ^~~~~
paint.cpp:58:7: warning: unused variable 'ans' [-Wunused-variable]
   58 |   int ans = 0;
      |       ^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 14 ms 31572 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 14 ms 31584 KB Output is correct
5 Correct 14 ms 31628 KB Output is correct
6 Correct 16 ms 31512 KB Output is correct
7 Correct 15 ms 31552 KB Output is correct
8 Correct 15 ms 31572 KB Output is correct
9 Execution timed out 1598 ms 31572 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 14 ms 31572 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 14 ms 31584 KB Output is correct
5 Correct 14 ms 31628 KB Output is correct
6 Correct 16 ms 31512 KB Output is correct
7 Correct 15 ms 31552 KB Output is correct
8 Correct 15 ms 31572 KB Output is correct
9 Execution timed out 1598 ms 31572 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 14 ms 31572 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 14 ms 31584 KB Output is correct
5 Correct 14 ms 31628 KB Output is correct
6 Correct 16 ms 31512 KB Output is correct
7 Correct 15 ms 31552 KB Output is correct
8 Correct 15 ms 31572 KB Output is correct
9 Execution timed out 1598 ms 31572 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 14 ms 31572 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 14 ms 31584 KB Output is correct
5 Correct 14 ms 31628 KB Output is correct
6 Correct 16 ms 31512 KB Output is correct
7 Correct 15 ms 31552 KB Output is correct
8 Correct 15 ms 31572 KB Output is correct
9 Execution timed out 1598 ms 31572 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 14 ms 31572 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 14 ms 31584 KB Output is correct
5 Correct 14 ms 31628 KB Output is correct
6 Correct 16 ms 31512 KB Output is correct
7 Correct 15 ms 31552 KB Output is correct
8 Correct 15 ms 31572 KB Output is correct
9 Execution timed out 1598 ms 31572 KB Time limit exceeded
10 Halted 0 ms 0 KB -