题解 [AGC007B] Construct Sequences

ETHANK · 2021-06-12 13:33:07 · 题解

构造题。先思考如何让 a_{p_i}+b_{p_i} 为定值，考虑到递增和递减的性质，不难发现 a_i=i,b_i=n-i 即满足要求。

下面让 a_{p_i}+b_{p_i} 递增即可，把 b_{p_i} 加上 i 就行了，但这会破坏我们 b_i 的递增性质。注意到两个数组同时乘以一个大数 k 后仍满足原性质，所以可以设 a_i=ki,b_i=k(n-i) 再把 b_{p_i} 加上 i 即可。只要 k\ge n 即满足要求，且 a_i,b_i\le 10^9 。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e4+5;
int a[N],b[N],n,p;
int main(){
    n=read();
    rep(i,1,n)a[i]=i*N,b[i]=(n-i)*N;
    rep(i,1,n)p=read(),b[p]+=i;
    rep(i,1,n)printf("%d ",a[i]);
    puts("");
    rep(i,1,n)printf("%d ",b[i]);
    return 0;
}