[CODEFORCES 1501C Going Home](https://codeforces.com/contest/1501/problem/C)
=

## 題目大意
給整數數列 $a$
找出**兩兩相異** $x, y, z, w$ 滿足 $a_x + a_y = a_z + a_w$
> 即 $x \not= y \not= z \not= w, y \not= w \not= x \not= z$

## 輸入
$n$ $(4 \le n \le 2\cdot 10^5)$，表示 $a$ 長度
$a_1, a_2, \cdots, a_n$ $(1 \le a_i \le 2.5\cdot 10^6)$

## 輸出
`YES` 表示存在解，反之 `NO`
若存在解，接著輸出一組 $x, y, z, w$
## 解法
令任意兩數相加 $S_{i,j} = a_i + a_j$

對於 $S_{z, w}$ 希望找到兩數 $a_x, a_y$ 使得 $S_{z, w} = S_{x, y}$
但 $x, y, z, w$ 有可能不滿足兩兩相異，所以得討論怎樣的情況能滿足這個條件

對某數 $S$，以**點**表示數列下標，**邊** $(x, y) \in E$ 表示 $S = a_x + a_y$，可觀察到圖：
- $E \ge 2$ 條邊，所有邊**沒有共同點**，則所有邊的點都兩兩相異
- $E \ge 2$ 條邊，所有邊**有共同點** $x$ 除了**某邊沒有** $x$，則該邊與某條邊的點兩兩相異
- $E \ge 4$ 條邊，所有邊**有共同點** $x$，則取 4 個 $x$ 的鄰點 $i_1, i_2, i_3, i_4$ 會滿足 $a_{i_1} + a_{i_2} = a_{i_3} + a_{i_4}$
> 因為 $a_{i_1} = a_{i_2} = a_{i_3} = a_{i_4}$

也就是說至多找出 **4 組相異[^diff]的數對**使得 $S_{i_1, j_1} = S_{i_2, j_2} = S_{i_3, j_3} = S_{i_4, j_4}$ 就有解了

兩數相加範圍 $[2\cdot\min\{a\}, 2\cdot\max\{a\}]$，總共 $N = 2\cdot\max\{a\} - 2\cdot\min\{a\} + 1$ 種相加後的和
因此根據**鴿籠原理**，枚舉 $3 \cdot N + 1$ 組相異數對，**至少**會有 4 組的和是**相同**的

所以至多只需枚舉 $\mathcal{O}(3\cdot N + 1) = \mathcal{O}(a_i)$ 個數對就能確定有沒有解

#include<bits/stdc++.h>
using namespace std;
 
int constexpr maxn = 2e5 + 10;
int constexpr maxa = 25e5 + 10;
 
int n, a[maxn];
 
int main()
{
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
 
  pair<int, int> vis[maxa*2] {};
  for(int i = 1; i <= n; i++)
    for(int j = i+1; j <= n; j++) {
      int sum = a[i] + a[j];
      auto& [_i, _j] = vis[sum];
 
      if(!_i) _i = i, _j = j;
      else if(_i != i && _i != j && _j != i && _j != j) {
        puts("YES");
        printf("%d %d %d %d\n", _i, _j, i, j);
 
        return 0;
      }
    }
 
  puts("NO");
 
  return 0;
}

[^diff]: $(x, y)$, $(z, w)$ 相異表示存在 $i \in (x, y), j \in (z, w)$ 有 $i \not= j$