B - Construct Sequences

解く前に考えてたこと

・配列の要素数を超える大きい公差を持った等差数列を考えて、順列 $P$ による差を相殺したい。
・具体例を考えるも、一般化できずに死亡、特に、入力 $n$ の値によって、数列を構築しようとしたのが問題かもしれない。

正解

$M = 40000$
$A_i = M(i+1)$
$B_i = M(n-i-1)$ などとすると、 $A_i +B_i = M(n)$ となる。つまり、添字 $i$ の値によらず一定である。
問題は $A_i + B_i$ もまた単調に増加する数列とする必要があるので、 $A_{P_i}$ の添字に $i$ を足してやる。 $M$ が巨大なので、問題なく数列を構築することができる。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? 1e9:1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){int b=0;for(auto itr :a){if(b++!=0)cout << " "; cout << itr;} }
using ll  = long long;
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
#define int ll
signed main(){
    int n; cin >> n;
    vector<int>p(n);  rep(i,n) cin >> p[i];
    vector<int>a(n),b(n);
    int maxi = 40000;
    rep(i,n){
        a[i] = maxi*(i+1);
        b[i] = maxi*(n-i-1)+1;
    }
    rep(i,n){
        a[p[i] - 1] += i;
    }
    join(a); cout << endl;
    join(b); cout << endl;
}