Overview

We calculate the area of each villager’s field and find the villager with the smallest index among those with the maximum area. In the provided code, we determine whether each villager satisfies the condition to be the answer by comparing them with all other villagers.

Analysis

The area of the field of the \(i\)-th villager is \(S_i = A_i \times B_i\), which is the product of its vertical and horizontal lengths.

If we only check whether the area is maximal, we might fail to choose the person with the smallest index when multiple villagers share the same maximum area. Therefore, we split the conditions for villager \(i\) to be the answer as follows:

• For villagers with a smaller index: There is no one with an area greater than or equal to \(S_i\).
• For villagers with a larger index: There is no one with an area strictly greater than \(S_i\).

A villager with a smaller index takes precedence even if their area is equal. On the other hand, against a villager with a larger index, villager \(i\) takes precedence even if their area is equal. For this reason, the comparison conditions differ before and after.

For example, consider the case where the areas are \([6, 12, 12]\) in order:

• Villager \(1\) is not the answer because there is someone after them with a strictly larger area.
• Villager \(2\) is the answer because there is no one before them with an area of at least \(12\), and no one after them with an area strictly greater than \(12\).
• Villager \(3\) is not the answer because villager \(2\) before them has the same area.

Even a naive approach that compares all pairs will easily run in time since \(N \leq 100\). Rather than optimizing for speed, it is more important to handle ties (equal areas) correctly.

Algorithm

1. Calculate the area of each villager’s field and store it in an array s.
2. Check the array index i in ascending order:
   • Set ok to true.
   • For all j satisfying j < i, if s[j] >= s[i], set ok to false.
   • For all j satisfying j > i, if s[j] > s[i], set ok to false.
   • If ok remains true until the end, output the villager’s number i + 1 and terminate.

No villager before or after has an area strictly larger than a villager who passes this check. Furthermore, there is no one with the same area and a smaller index. Therefore, the output will be “the villager with the smallest index among those with the maximum area.”

Conversely, the villager that is the correct answer will always satisfy this condition, so the answer is guaranteed to be found.

Complexity

• Time complexity: \(O(N^2)\)
  Each villager is compared with up to \(N-1\) other villagers.
• Space complexity: \(O(N)\)
  We store the areas of all villagers’ fields in an array.

Implementation Points

• Use >= for preceding villagers and > for succeeding villagers. This distinction is crucial to prioritize the smaller index when areas are equal.

• Array indices are 0-based, but villager numbers are 1-based, so the output is i + 1.

• The maximum possible area is \(1000 \times 1000 = 10^6\). In the provided code, the areas and side lengths are handled using the long long type.

  Source Code

// 問題文から独立に実装: 各村人について「自分より前に自分以上の面積がなく、後ろに自分より大きい面積がない」か調べる
#include <iostream>
#include <vector>
int main() {
    int n; std::cin >> n;
    std::vector<long long> s(n);
    for (int i = 0; i < n; ++i) { long long a, b; std::cin >> a >> b; s[i] = a * b; }
    for (int i = 0; i < n; ++i) {
        bool ok = true;
        for (int j = 0; j < i; ++j) if (s[j] >= s[i]) ok = false;
        for (int j = i + 1; j < n; ++j) if (s[j] > s[i]) ok = false;
        if (ok) { std::cout << i + 1 << std::endl; return 0; }
    }
}

---

This editorial was generated by gpt-6-astra-medium.