Apartment hunting
user_3741288
c_cpp
2 years ago
1.2 kB
10
Indexable
#include <unordered_map>
#include <vector>
using namespace std;
void func(vector<unordered_map<string, int>>& dp, vector<unordered_map<string, bool>>& blocks, int st, int inc) {
unordered_map<string, int> temp;
for(int i=st; i>=0 && i<blocks.size(); i=i+inc) {
unordered_map<string, int> temp1 = temp;
for(auto ele=blocks[i].begin(); ele!=blocks[i].end();ele++) {
if(temp1.find(ele->first) == temp1.end()) {
temp1[ele->first] = ele->second == true ? i : INT_MAX;
} else {
temp1[ele->first] = ele->second == true ? i : temp1[ele->first];
}
}
temp = temp1;
dp[i] = temp1;
}
}
int apartmentHunting(
vector<unordered_map<string, bool>> blocks, vector<string> reqs
) {
int n=blocks.size();
vector<unordered_map<string, int>> dp1(n), dp2(n);
func(dp1, blocks, 0, 1);
func(dp2, blocks, blocks.size()-1, -1);
int ind=0, mini=INT_MAX;
for(int i=0;i<n;i++) {
int l_max = 0;
for(int j=0;j<reqs.size();j++) {
l_max = max(l_max, min(abs(i-dp1[i][reqs[j]]), abs(i-dp2[i][reqs[j]])));
}
if(l_max < mini) {
mini = l_max;
ind = i;
}
}
return ind;
}
Editor is loading...
Leave a Comment