HjHimansh

Buildings

Jan 16th, 2022 (edited)
273
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int apartmentHunting(vector<unordered_map<string, bool>> blocks, vector<string> reqs){
  5.     if(blocks.empty()) return -1;
  6.  
  7.     vector<pair<unordered_map<string, int>, int>> distance(blocks.size());
  8.  
  9.  
  10.     // distance[i].first[building] returns minimum distance of building from block[i]
  11.     // distance[i].second returns the maximum distance among all building from block[i]
  12.     // we have to return the i which has minimum distance[i].second
  13.  
  14.     unordered_map<string, int> aboveMaxIndex;
  15.  
  16.     for(int i=0; i<blocks.size(); i++){
  17.         for(auto &x: reqs){
  18.             if(blocks[i][x]){
  19.                 distance[i].first[x] = 0;
  20.             }
  21.             else if(aboveMaxIndex.count(x)){
  22.                 distance[i].first[x] = i-aboveMaxIndex[x];
  23.             }
  24.         }
  25.  
  26.         // aboveMinIndex[building] contains the maximum index < i at which contains the building
  27.         for(auto it=blocks[i].begin(); it!=blocks[i].end(); it++){
  28.             if(it->second){
  29.                 //i.e current block has building it->first
  30.                 aboveMaxIndex[it->first] = i;
  31.             }
  32.         }
  33.  
  34.     }
  35.  
  36.     unordered_map<string, int> bottomMinIndex;
  37.     for(int i=blocks.size()-1; i>=0; i--){
  38.  
  39.         for(auto &x: reqs){
  40.             if(bottomMinIndex.count(x)){
  41.                 if(distance[i].first.count(x)){
  42.                     distance[i].first[x] = min(distance[i].first[x], bottomMinIndex[x]-i);
  43.                 }
  44.                 else{
  45.                     distance[i].first[x] = bottomMinIndex[x]-i;
  46.                 }
  47.             }
  48.         }
  49.  
  50.         // bottomMinIndex[building] contains the minimum index > i at which contains the building
  51.         for(auto it=blocks[i].begin(); it!=blocks[i].end(); it++){
  52.             if(it->second){
  53.                 //i.e current block has building it->first
  54.                 bottomMinIndex[it->first] = i;
  55.             }
  56.         }
  57.     }
  58.  
  59.     if(distance[0].first.size() < reqs.size()){
  60.         //i.e there is atleast one requirement present in none of the buildings
  61.         cout << distance[0].first.size() << endl;
  62.         return -1;
  63.     }
  64.  
  65.     for(int i=0; i<distance.size(); i++){
  66.         int farthestDistance = 0;
  67.         for(auto it=distance[i].first.begin(); it!=distance[i].first.end(); it++){
  68.             farthestDistance = max(farthestDistance, it->second);
  69.         }
  70.         distance[i].second = farthestDistance;
  71.     }
  72.  
  73.     int answer = -1;
  74.     int minFarthestDistance = INT_MAX;
  75.     for(int i=0; i<distance.size(); i++){
  76.         if(distance[i].second < minFarthestDistance){
  77.             minFarthestDistance = distance[i].second;
  78.             answer = i;
  79.         }
  80.     }
  81.  
  82.     return answer;
  83. }
  84.  
  85. int main(){
  86.     vector<unordered_map<string, bool>> blocks(5);
  87.     blocks[0]["gym"] = false;
  88.     blocks[0]["school"] = true;
  89.     blocks[0]["store"] = false;
  90.  
  91.     blocks[1]["gym"] = true;
  92.     blocks[1]["school"] = false;
  93.     blocks[1]["store"] = false;
  94.  
  95.     blocks[2]["gym"] = true;
  96.     blocks[2]["school"] = true;
  97.     blocks[2]["store"] = false;
  98.  
  99.     blocks[3]["gym"] = false;
  100.     blocks[3]["school"] = true;
  101.     blocks[3]["store"] = false;
  102.  
  103.     blocks[4]["gym"] = false;
  104.     blocks[4]["school"] = true;
  105.     blocks[4]["store"] = true;
  106.  
  107.     vector<string> reqs = {"gym", "school", "store"};
  108.     cout << apartmentHunting(blocks, reqs) << endl;
  109.    
  110. }
RAW Paste Data Copied