2026年 北马其顿编程竞赛 (Macedonian programming contests 2026)

赛事等级： 校级选拔赛 (School competition)
内容类型： 竞赛题目 (Competition tasks)

题目名称：多边形内的线段 (Отсечки во многуаголник)

题目描述

在一个具有 $N$ 个顶点的正多边形上，每个顶点都标记了一个正整数（范围在 $1$ 到 $1,000,000,000$ 之间）。对于从第 $1$ 个到第 $N$ 个顶点，输入给出了相应的数值 $A_i$。

布莱里姆（Blerim）的任务是用红色线段（可以是多边形的边或对角线）连接所有具有相同数值的顶点。

你的任务是：为每一个顶点确定从该点发出的最长线段的长度。 为了方便计算，我们定义线段的“长度”如下：

• 长度 = 被该线段分割出的两个顶点弧中，顶点数较少的那一侧的顶点数 + 1。
• 或者可以理解为：在环形结构上，两个顶点之间的最短距离（步数）。
• 如果某个顶点的数值是唯一的（没有其他顶点与其数值相同），则认为没有线段从该点发出，其值为 $0$。

输入格式

• 第一行包含一个整数 $N$ ($0 < N \le 100,000$)，代表多边形的顶点数。
• 第二行包含 $N$ 个整数 $A_i$ ($1 \le A_i < 1,000,000,000$)，按顺时针或逆时针顺序排列的顶点数值，由空格分隔。

注意： 对于 40% 的数据，$N \le 5,000$。

输出格式

• 输出 $N$ 个整数，由空格分隔。按照输入中顶点的顺序，依次输出每个顶点发出的最长线段长度。

限制条件

• 时间限制： 500 毫秒
• 内存限制： 16 MB（注意：内存限制较为严格）

样例说明

• 输入：

  6
  1 1 2 1 2 3
  

• 输出：

  3 2 2 3 2 0
  

• 解释：
  • 顶点 1 (值1)：与其值相同的有顶点 2 和 4。距离分别为 1 和 3。最长为 3。
  • 顶点 2 (值1)：与其值相同的有顶点 1 和 4。距离分别为 1 和 2。最长为 2。
  • 顶点 3 (值2)：与其值相同的有顶点 5。距离为 2。最长为 2。
  • 顶点 4 (值1)：与其值相同的有顶点 1 和 2。距离分别为 3 和 2。最长为 3。
  • 顶点 5 (值2)：与其值相同的有顶点 3。距离为 2。最长为 2。
  • 顶点 6 (值3)：唯一值，输出 0。

版权及来源信息

• 项目： Macedonian Programming Contests (北马其顿编程竞赛)
• 年份： 2026
• 主办/版权方： Združenie na informatičari na Makedonija (ZIM / 北马其顿计算机科学家协会)
• 语言： 马其顿语 (Original in Macedonian)