[Construct Sequences] 构造

Description

You are given a permutation p of the set ({1,2,...,N}). Please construct two sequences of positive integers (a_1, a_2, ..., a_N) and (b_1, b_2, ..., b_N) satisfying the following conditions:
·(1≤a_i,b_i≤10^9) for all (i)
·(a_1<a_2<...<a_N)
·(b_1>b_2>...>b_N)
·(a_{p_1}+b_{p_1}<a_{p_2}+b_{p_2}<...<a_{p_N}+b_{p_N})

Constraints
·(2≤N≤20,000)
·(p) is a permutation of the set ({1,2,...,N})

Solution

注意到a，b分别是递增和递减的，不妨先按照等差数列构造，首先保证(a_i+b_i)不变，然后再按照给如的序列p在a序列的基础上减去一个相对较小的值，保证不会改变原有的单调性，这样就改变了(a_i+b_i)的单调性

Note

第一次选值的时候选取了20000，由于太大而影响了最总的结果，这里选择N然后令其递减即可

Code

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int p[20000 + 10];

int a[20000 + 10], b[20000 + 10];
int main() {
	//freopen("test.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N; 
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> p[i];
	for (int i = 1; i <= N; i++) a[i] = i*20001;
	for (int i = N; i >= 1; i--) b[N-i+1] = i*20001;
	int base = N;
	for (int i = 1; i <= N; i++) {
		a[p[i]] -= base;
		base--;
	}
	for (int i = 1; i <= N; i++) cout << a[i] << " ";
	cout << endl;
	for (int i = 1; i <= N; i++) cout << b[i] << " ";
	return 0;
}