#P15533. [HNOI2026省队集训]潮水(tide)

[HNOI2026省队集训]潮水(tide)

题目描述

对于两个排列 a1⋯n,b1⋯na_{1\cdots n}, b_{1\cdots n},令

$$f(a, b) = \max_{i=1}^n \lvert \sqrt i + \sqrt{a_i}+\sqrt{b_i}-2\sqrt n\rvert$$

构造 a,ba, b 满足 f(a,b)≤2.5f(a, b) \leq 2.5。

输入格式

第一行一个正整数 nn。

输出格式

两行,每行各 nn 个正整数,分别表示 a1⋯na_{1\cdots n} 和 b1⋯nb_{1\cdots n}。

输入数据 1

3

[Copy](javascript:;)

输出数据 1

2 3 1
3 1 2

[Copy](javascript:;)

数据范围

对于所有数据,保证 1≤n≤1061\leq n \leq 10^6。

在单个测试点中,设选手构造出的 f(a,b)f(a, b) 为 xx,则选手在该测试点的得分为

max⁡(0,5−98ln⁡max⁡(x,2.5)2.5)\max(0, 5-\frac 98\ln\frac{\max(x, 2.5)}{2.5})
  • 测试点 11,保证 n=6n = 6。
  • 测试点 2,32, 3,保证 n≤10n \leq 10。
  • 测试点 4∼64 \sim 6,保证 n≤100n \leq 100。
  • 测试点 7∼127 \sim 12,保证存在 mm 使得 n=(m2)n = \binom{m}{2}。
  • 测试点 13∼1613 \sim 16,保证 n≤104n \leq 10^4。
  • 测试点 17∼2017 \sim 20,无特殊限制。

samples

solution