← 返回题目列表

AtCoder · agc074_c

C. 波拉利斯

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

给你一个正整数 N.
输出一对非负整数序列 P=(P_1, P_2, \dots,P_N), A=(A_1, A_2, \dots,A_N) 满足以下所有条件:

  • 0 \leq P_i < 2^{30}~(1 \leq i \leq N)
  • 0 \leq A_i < 2^{30}~(1 \leq i \leq N)
  • 的最长严格递增子序列的长度 (P_1~\mathrm{OR}~A_i, P_2~\mathrm{OR}~A_i, \dots, P_N~\mathrm{OR}~A_i) is i. (1 \leq i \leq N)
    • \mathrm{OR} 表示按位 \mathrm{OR} 操作。

可以证明,在该问题的约束下,至少存在一对 P, A 满足条件。

解决 T 每个输入的测试用例。

什么是按位 \mathrm{OR}?

按位 \mathrm{OR} 非负整数 A, B,表示 A\ \mathrm{OR}\ B,定义如下:

  • 当 A\ \mathrm{OR}\ B 以二进制形式写入,位置处的数字 2^k (k \geq 0) 是 1 如果位置处至少有一位数字 2^k 的二进制表示形式 A 和 B is 1,和 0 否则。
例如, 3\ \mathrm{OR}\ 5 = 7 (二进制: 011\ \mathrm{OR}\ 101 = 111).

约束

  • 1 \leq T
  • 1 \leq N \leq 1024
  • 对于单个输入中的测试用例, N 最多是 200000.
  • 对于单个输入中的测试用例, N^2 最多是 1024^2.
  • 所有输入值均为整数。

输入

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个案例均按以下格式给出:

N

输出

输出一个解决方案 \mathrm{case}_1, \mathrm{case}_2, \dots, \mathrm{case}_T 按此顺序。

对于每种情况,按以下格式输出答案:

P_1 P_2 \ldots P_N
A_1 A_2 \ldots A_N

如果有多个解决方案,则其中任何一个都将被视为正确。


示例输入 1

3
3
8
1

示例输出 1

3 14 5
13 2 10
6 902 909 186 684 219 471 248
1023 249 64 0 264 768 778 794
2025
1026

对于第一个测试用例,示例输出为 P = (3, 14, 5), A = (13, 2, 10).

  • 一个最长的严格递增子序列 (3~\mathrm{OR}~13, 14~\mathrm{OR}~13, 5~\mathrm{OR}~13) = (15, 15, 13) is (13),其长度为 1.
  • 一个最长的严格递增子序列 (3~\mathrm{OR}~2, 14~\mathrm{OR}~2, 5~\mathrm{OR}~2) = (3, 14, 7) is (3, 7),其长度为 2.
  • 一个最长的严格递增子序列 (3~\mathrm{OR}~10, 14~\mathrm{OR}~10, 5~\mathrm{OR}~10) = (11, 14, 15) is (11, 14, 15),其长度为 3.

由上可以确认 P = (3, 14, 5), A = (13, 2, 10) 满足条件。