AT_agc079_c.Sort by Queue and Reverse

NOI/NOI+/CTSC

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a permutation P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N) of (1,2,…,N)(1,2,\ldots,N). Additionally, there is a queue that is initially empty.

You can perform the following three types of operations any number of times, in any order.

  • Append operation: If PP is not empty, remove the first element of PP and add that element to the end of the queue.
  • Output operation: If the queue is not empty, remove the front element and output its value.
  • Reverse operation: Reverse the order of the elements in the queue. That is, if the elements of the queue are currently (v1,v2,…,vk)(v_1,v_2,\ldots,v_k), replace them with (vk,vk−1,…,v1)(v_k,v_{k-1},\ldots,v_1).

You want to output all elements so that the output values are 1,2,…,N1,2,\ldots,N in this order.

Determine whether this is possible. If it is possible, find the minimum number of reverse operations required.

You are given TT test cases; solve each of them.

给你一个 (1,2,…,N)(1,2,\ldots,N) 的排列 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N)。此外,还有一个初始为空的队列。

你可以以任意顺序、任意次数执行以下三种操作:

  • 追加操作:若 PP 非空,则移除 PP 的第一个元素,并将该元素添加到队列尾部。
  • 输出操作:若队列非空,则移除队列前端的元素,并输出其值。
  • 翻转操作:翻转队列中元素的顺序。即,若当前队列中的元素为 (v1,v2,…,vk)(v_1,v_2,\ldots,v_k),则将其替换为 (vk,vk−1,…,v1)(v_k,v_{k-1},\ldots,v_1)。

你的目标是输出全部元素,使得输出序列恰好为 1,2,…,N1,2,\ldots,N(按此顺序)。

请判断是否可行。若可行,求出所需的最少翻转操作次数。

你将得到 TT 组测试用例,请对每组用例求解。

输入格式

The input is given from Standard Input in the following format:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

Each test case is given in the following format:

NN
P1P_1 P2P_2 …\ldots PNP_N

输入从标准输入中按以下格式给出:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

每个测试用例按以下格式给出:

NN
P1P_1 P2P_2 …\ldots PNP_N

输出格式

For each test case, output the minimum number of reverse operations required if it is possible to make the output values 1,2,…,N1,2,\ldots,N in this order, and -1 otherwise.

对于每个测试用例,如果能够通过若干次翻转操作使得输出值按顺序为 1,2,…,N1,2,\ldots,N,则输出所需的最少翻转操作次数;否则输出 -1。

输入输出样例

  • 输入#1

    10
    4
    3 2 4 1
    5
    2 4 3 5 1
    1
    1
    4
    1 2 3 4
    5
    5 4 3 2 1
    8
    2 1 4 3 6 5 8 7
    2
    2 1
    1
    1
    9
    2 8 3 5 6 7 1 9 4
    3
    2 3 1

    输出#1

    3
    -1
    0
    0
    1
    4
    1
    0
    -1
    2

说明/提示

Sample 1 Explanation:
In the first test case, for example, you can perform the operations as follows.

Operation

Queue after the operation

Values output so far

Append operation ×2\times 2

(3,2)(3,2)

None

Reverse operation

(2,3)(2,3)

None

Append operation ×2\times 2

(2,3,4,1)(2,3,4,1)

None

Reverse operation

(1,4,3,2)(1,4,3,2)

None

Output operation

(4,3,2)(4,3,2)

11

Reverse operation

(2,3,4)(2,3,4)

11

Output operation ×3\times 3

Empty

1,2,3,41,2,3,4

This performs the reverse operation 33 times. It cannot be achieved with 22 or fewer reverse operations, so the answer is 33.

Constraints

  • 1≤T≤2500001 \leq T \leq 250000
  • 1≤N≤2500001 \leq N \leq 250000
  • 1≤Pi≤N1 \leq P_i \leq N (1≤i≤N)(1 \leq i \leq N)
  • P1,P2,…,PNP_1,P_2,\ldots,P_N are pairwise distinct.
  • The sum of NN over all test cases in a single input is at most 250000250000.
  • All input values are integers.

样例 1 解释:
在第一个测试用例中,例如,你可以按如下方式执行操作。

操作 操作后的队列 当前已输出的值
追加操作 ×2\times 2 (3,2)(3,2) 无
翻转操作 (2,3)(2,3) 无
追加操作 ×2\times 2 (2,3,4,1)(2,3,4,1) 无
翻转操作 (1,4,3,2)(1,4,3,2) 无
输出操作 (4,3,2)(4,3,2) 11
翻转操作 (2,3,4)(2,3,4) 11
输出操作 ×3\times 3 空 1,2,3,41,2,3,4

该方案共执行了 33 次翻转操作。无法仅用 22 次或更少的翻转操作完成,因此答案为 33。

约束条件

  • 1≤T≤2500001 \leq T \leq 250000
  • 1≤N≤2500001 \leq N \leq 250000
  • 1≤Pi≤N1 \leq P_i \leq N (1≤i≤N)(1 \leq i \leq N)
  • P1,P2,…,PNP_1,P_2,\ldots,P_N 两两互不相同。
  • 单组输入中所有测试用例的 NN 值之和不超过 250000250000。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页