Looksery Cup 2015, problem: (G) Happy Line

pi < pj => ai+i < aj+j
我覺得我真太廢惹，為啥比賽時弄不出來啦QAQQQ

--聽說寫結論題要寫證明，那就留個證明--

讓a[i]為該陣列，p[i]是a[i]移動後的位置
則p[i] < p[j] if and only if a[i]-p[i]+i < a[j]-p[j]+j

to pf: p[i] < p[j] if and only if a[i]+i < a[j]+j

左到右：  o.k.

右到左：

assume p[i] >= p[j]
~> a[i]-p[i]+i >= a[j]-p[j]+j
~>a[i]+i >= a[j]+j  -X-

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <map>
#include <cmath>
#include <utility>

using namespace std;


int ans[200000];
struct pack{
    int val;
    int index;
}ps[200000];

bool operator<(const pack& pa, const pack& pb){
    return pa.val < pb.val;
}

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++){
        int inp; scanf("%d", &inp);
        ps[lx].val = inp + lx;
        ps[lx].index = lx;
    }
    sort(ps, ps+n);
    bool check = true;
    for(int lx = 1;lx < n and check;lx++)
        check = ps[lx].val != ps[lx-1].val;
    if(not check){
        puts(":(");
        return 0;
    }

    for(int lx = 0;lx < n;lx++)
        ans[ps[lx].index] = ps[lx].val-lx;
    sort(ans, ans+n);
    for(int lx = 0;lx < n;lx++)
        printf("%d ", ans[lx]);
    puts("");
    return 0;
}