「WHOI-4」加减法构造

Luogu
IDLGP8963
Time2000ms
Memory512MB
DifficultyP5
数学Special JudgeO2优化
小 W 给了你一个长度为 $n$ 的**整数**数组 $x$。你需要构造一个长度也为 $n$ 的**整数**数组 $y$,并满足: 1. $\forall 1\le i,j,i+j\le n,y_{i+j}=y_i+y_j+k$,$k$ 是一个你需要钦定的整数。 3. $d(x,y)=\sum\limits_{i=1}^n|x_i-y_i|$ 最小。 3. $-V\le y_i\le V$,$V$ 是输入中给定的数。 ## Input 第一行两个整数 $n,V$。 接下来一行 $n$ 个整数,第 $i$ 个代表 $x_i$。 ## Output 第一行两个整数 $k,d$,代表你钦定的值和你的答案。 接下来一行 $n$ 个整数,第 $i$ 个代表 $y_i$。 题目保证 $d$ 的最小值在 `long long` 范围内。 [samples] ## Note **数据范围** - Subtask 1($20$ pts):$n\le10$,$ V\le10$,$ |x_i|\le10$; - Subtask 2($20$ pts):$n\le100$,$ |x_i|\le100$,$V\le1000$; - Subtask 3($20$ pts):$n\le10^6$,$ |x_i|\le10^6$,$V=10^{12}$; - Subtask 4($20$ pts):$n\le10^7$,$|x_i|\le10^7$,$V\le10^7$; - Subtask 5($20$ pts):$n\le10^7$,$|x_i|\le10^7$,$V\le 10^{12}$。 对于所有数据,保证 $1\le n\le 10^7$,$|x_i|\le10^7$,$1\le V\le10^{12}$。 **关于 Special Judge 的说明** 对于每个测试点: 如果你输出的格式不正确,你将会获得 $0$ 分。 如果你输出的数中有不在 $[-V,V]$ 范围的数,你将会获得 $0$ 分。 如果你的数列 $y$ 不符合你输出的 $k$,你将会获得 $0$ 分。 如果你的数列 $y$ 不符合你输出的 $d$,你将会获得 $0$ 分。 否则你将会获得的分数为该测试点总分的百分之 $\max\{0,\min\{100,10100-\frac{10000d}{d'}\}\}$,$d'$ 是答案的 $d$ 值。
Samples
Input #1
5 10
2 3 8 5 4
Output #1
-1 6
2 3 4 5 6
Input #2
7 100
11 45 14 19 19 8 10
Output #2
-17 51
16 15 14 13 12 11 10
API Response (JSON)
{
  "problem": {
    "name": "「WHOI-4」加减法构造",
    "description": {
      "content": "小 W 给了你一个长度为 $n$ 的**整数**数组 $x$。你需要构造一个长度也为 $n$ 的**整数**数组 $y$,并满足: 1. $\\forall 1\\le i,j,i+j\\le n,y_{i+j}=y_i+y_j+k$,$k$ 是一个你需要钦定的整数。 3. $d(x,y)=\\sum\\limits_{i=1}^n|x_i-y_i|$ 最小。 3. $-V\\le y_i\\le V$,$V",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8963"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 W 给了你一个长度为 $n$ 的**整数**数组 $x$。你需要构造一个长度也为 $n$ 的**整数**数组 $y$,并满足:\n\n1. $\\forall 1\\le i,j,i+j\\le n,y_{i+j}=y_i+y_j+k$,$k$ 是一个你需要钦定的整数。\n3. $d(x,y)=\\sum\\limits_{i=1}^n|x_i-y_i|$ 最小。\n3. $-V\\le y_i\\le V$,$V...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments