[PA 2022] Podwyżki

Luogu
IDLGP9255
Time2000ms
Memory512MB
DifficultyP4
2022Special JudgePA(波兰)
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 2 [Podwyżki](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/pod/)** 对于 Bytecorp 来说,2022 年是艰难的一年。商业决策失误,再加上不景气的市场状况,意味着公司无力为员工涨薪。为了准备应对员工提出的不舒服的问题,人资部门发明了一种方法来证明员工不值得涨薪。 根据一个雇员在连续几天内产生的总收益,可以将一年(在 Byteotia,一年不一定是 365 天)划分为若干区间,这将表明该雇员工作不投入。更确切地说,人资部门希望将收入序列划分为 $k$ 个连续区间,使得序列中的每个元素都恰好属于一个区间。如果**不可能**从每个区间选择一个元素,使所选元素形成严格的升序,那么这种划分是正确的。 Bytecorp 的未来在你手上。写一个程序读入某个雇员产生的收益序列和一个整数 $k$,并根据人资部门的要求把序列分成 $k$ 段,或者判断无法分成这样的 $k$ 段。 ## Input 输入的第一行包含两个整数 $n,k$,表示序列长度和要分成的段数。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$,表示收益序列。 ## Output 如果这个序列不能按如上方法分割,输出一行一个字符串 `NIE`。 否则输出两行,第一行一个字符串 `TAK`,第二行输出 $k-1$ 个整数 $v_1,\ldots,v_{k-1}$,表示正确的划分中除最后一个区间外,每个连续区间的右端点,最后一个区间的右端点一定是 $n$。 如果有多个正确答案,可以输出任意一个。 [samples] ## Note 对于 $100\%$ 的数据,满足: $2\le k\le n\le 5 \times 10 ^ 5, 1\le a_i\le 10^9, 1\le v_i<n,v_i<v_{i+1}$。
Samples
Input #1
6 3
3 5 4 8 3 7
Output #1
TAK
3 5
Input #2
4 2
2 3 2 3
Output #2
NIE
API Response (JSON)
{
  "problem": {
    "name": "[PA 2022] Podwyżki",
    "description": {
      "content": "**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 2 [Podwyżki](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/pod/)** 对于 Bytecorp 来说,2022 年是艰难的一年。商业决策失误,再加上不景气的市场状况,意味着公司无力为员工涨薪。为了准备应",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9255"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 2 [Podwyżki](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/pod/)**\n\n对于 Bytecorp 来说,2022 年是艰难的一年。商业决策失误,再加上不景气的市场状况,意味着公司无力为员工涨薪。为了准备应...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments