class Solution {
public:
Solution(vector<vector<int>>& rects) {
}
vector<int> pick() {
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(rects);
* vector<int> param_1 = obj->pick();
*/
class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = rects
self.presum = [0]
for a, b, x, y in rects:
self.presum.append(self.presum[-1] + (x - a + 1) * (y - b + 1))
def pick(self) -> List[int]:
rdm = random.randint(0, self.presum[-1] - 1)
idx = bisect_right(self.presum, rdm) - 1
a, b, x, y = self.rects[idx]
v = rdm - self.presum[idx]
return [a + v % (w := x - a + 1), b + v // w]
# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
/**
* @param {number[][]} rects
*/
var Solution = function(rects) {
this.arr = [0];
this.rects = rects;
for (const rect of rects) {
const a = rect[0], b = rect[1], x = rect[2], y = rect[3];
this.arr.push(this.arr[this.arr.length - 1] + (x - a + 1) * (y - b + 1));
}
};
/**
* @return {number[]}
*/
Solution.prototype.pick = function() {
let k = Math.floor(Math.random() * this.arr[this.arr.length - 1]);
const rectIndex = binarySearch(this.arr, k + 1) - 1;
k -= this.arr[rectIndex];
const rect = this.rects[rectIndex];
const a = rect[0], b = rect[1], y = rect[3];
const col = y - b + 1;
const da = Math.floor(k / col);
const db = k - col * da;
return [a + da, b + db];
};
const binarySearch = (arr, target) => {
let low = 0, high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((high - low) / 2) + low;
const num = arr[mid];
if (num === target) {
return mid;
} else if (num > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
}
/**
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(rects)
* var param_1 = obj.pick()
*/
type Solution struct {
rects [][]int
sum []int
}
func Constructor(rects [][]int) Solution {
sum := make([]int, len(rects)+1)
for i, r := range rects {
a, b, x, y := r[0], r[1], r[2], r[3]
sum[i+1] = sum[i] + (x-a+1)*(y-b+1)
}
return Solution{rects, sum}
}
func (s *Solution) Pick() []int {
k := rand.Intn(s.sum[len(s.sum)-1])
rectIndex := sort.SearchInts(s.sum, k+1) - 1
r := s.rects[rectIndex]
a, b, y := r[0], r[1], r[3]
da := (k - s.sum[rectIndex]) / (y - b + 1)
db := (k - s.sum[rectIndex]) % (y - b + 1)
return []int{a + da, b + db}
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(rects);
* param_1 := obj.Pick();
*/
class Solution {
public:
Solution(vector<vector<int>>& rects) : rects{rects} {
this->arr.emplace_back(0);
for (auto & rect : rects) {
this->arr.emplace_back(arr.back() + (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1));
}
}
vector<int> pick() {
uniform_int_distribution<int> dis(0, arr.back() - 1);
int k = dis(gen) % arr.back();
int rectIndex = upper_bound(arr.begin(), arr.end(), k) - arr.begin() - 1;
k = k - arr[rectIndex];
int a = rects[rectIndex][0], b = rects[rectIndex][1];
int y = rects[rectIndex][3];
int col = y - b + 1;
int da = k / col;
int db = k - col * da;
return {a + da, b + db};
}
private:
vector<int> arr;
vector<vector<int>>& rects;
mt19937 gen{random_device{}()};
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(rects);
* vector<int> param_1 = obj->pick();
*/
class Solution {
Random rand;
List<Integer> arr;
int[][] rects;
public Solution(int[][] rects) {
rand = new Random();
arr = new ArrayList<Integer>();
arr.add(0);
this.rects = rects;
for (int[] rect : rects) {
int a = rect[0], b = rect[1], x = rect[2], y = rect[3];
arr.add(arr.get(arr.size() - 1) + (x - a + 1) * (y - b + 1));
}
}
public int[] pick() {
int k = rand.nextInt(arr.get(arr.size() - 1));
int rectIndex = binarySearch(arr, k + 1) - 1;
k -= arr.get(rectIndex);
int[] rect = rects[rectIndex];
int a = rect[0], b = rect[1], y = rect[3];
int col = y - b + 1;
int da = k / col;
int db = k - col * da;
return new int[]{a + da, b + db};
}
private int binarySearch(List<Integer> arr, int target) {
int low = 0, high = arr.size() - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int num = arr.get(mid);
if (num == target) {
return mid;
} else if (num > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(rects);
* int[] param_1 = obj.pick();
*/
class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = rects
self.sum = [0]
for a, b, x, y in rects:
self.sum.append(self.sum[-1] + (x - a + 1) * (y - b + 1))
def pick(self) -> List[int]:
k = randrange(self.sum[-1])
rectIndex = bisect_right(self.sum, k) - 1
a, b, _, y = self.rects[rectIndex]
da, db = divmod(k - self.sum[rectIndex], y - b + 1)
return [a + da, b + db]
# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
