Nearest Neighbor Image Retrieval by Embedding

Problem You have an image database where each image is represented by a d-dimensional embedding. Given a query embedding q, find the most similar image. Similarity is cosine similarity: [ \text{sim}(a,b) = \frac{a\cdot b}{|a|,|b|} ] Return the index (0-based) of the image with the highest similarity; break ties by smaller index. Input First line: integers n d Next n lines: d floats, embedding of image i Last line: d floats, query vector q Output Print one integer: the index of the most similar image. Constraints 1 <= n <= 200000 1 <= d <= 512 Elements are floats with abs value <= 1e3 All vectors have non-zero norm Example Input: 3 2 1 0 0 1 1 1 1 0.2 Output: 0 Example Input 1 3 1 2 3 1 2 3 Output 0