b062:
Luminescence
Content
这是 b059 もぺもぺ 的困难版本。
为了关停PhigrOS，统治局设计了乱序算法。乱序算法在PhigrOS中的体现便是幽蓝边界。幽蓝边界从巴别起便一直向像素塔的顶层吞噬而去。
被吞入幽蓝边界的人的数据会被乱序算法打乱。但作为碎数研 Firework Data Patcher 项目的负责人，你的任务便是复原这些数据。
统治局的乱序算法如下：
一个人的数据为一个长度为n的数列a，
算法总共会对a进行m轮乱序。
在每轮乱序中，算法新建一个数列b，并把a分为前半部分与后半部分。接着把后半部分最前的数字插入到b的最后，再把前半部分最前的数字插入到b的最后，如此交替下去。最后，算法把数列b的数字覆盖a原本的数字。
碎数研可以获得的信息只有数据的的长度和乱序的轮数，现在你需要尝试找出数据乱序后的第k个数是原本数列的第几个数。
Input
有多组测资。
第一行包含一个整数 t —— 测资数量
对于每组测资，
第一行包括三个整数：n, m, k —— 数据长度，乱序轮数，目标数据的下标
保证n为偶数
Output
对于每组测资输出一个整数 —— 乱序后的第k个数据在原数据的下标。
Sample Input
#1
1 6 2 3
Sample Output
#1
6
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (10%): 1.0s , <50M
不公開 測資點#1 (10%): 1.0s , <50M
不公開 測資點#2 (10%): 1.0s , <50M
不公開 測資點#3 (10%): 1.0s , <50M
不公開 測資點#4 (10%): 1.0s , <50M
不公開 測資點#5 (10%): 1.0s , <50M
不公開 測資點#6 (10%): 1.0s , <50M
不公開 測資點#7 (10%): 1.0s , <50M
不公開 測資點#8 (10%): 1.0s , <50M
不公開 測資點#9 (10%): 1.0s , <50M
不公開 測資點#0 (10%): 1.0s , <50M
不公開 測資點#1 (10%): 1.0s , <50M
不公開 測資點#2 (10%): 1.0s , <50M
不公開 測資點#3 (10%): 1.0s , <50M
不公開 測資點#4 (10%): 1.0s , <50M
不公開 測資點#5 (10%): 1.0s , <50M
不公開 測資點#6 (10%): 1.0s , <50M
不公開 測資點#7 (10%): 1.0s , <50M
不公開 測資點#8 (10%): 1.0s , <50M
不公開 測資點#9 (10%): 1.0s , <50M
Hint ：
范例一解释：
[1, 2, 3, 4, 5, 6] -> [4, 1, 5, 2, 6, 3] -> [2, 4, 6, 1, 3, 5]
乱序后第3个数字应是原本数据的第6个数字
本題測資較大，請使用較快的I/O方法。
1 ≤ t < 105
1 ≤ k ≤ n < 109
1 ≤ m < 109
Tags:
出處:
[管理者：
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||