Chinese

gistfile1.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
using namespace std;

const int INF=INT_MAX/2;
vector<int> dstmp;
int ds3[300000];
int len[200010];
int mins[100000];
int mins2[100000];
int minmin[100000];
int main(){
    int N;
    scanf("%d",&N);
    int a;
    for(int i=1;i<=N-1;i++){
        scanf("%d",&a);
        a--;
        dstmp.PB(((a-i)+N)%N);
    }
    {
        sort(ALL(dstmp));
        dstmp.erase(unique(ALL(dstmp)),dstmp.end());
        int dss=dstmp.size();
        for(int i=0;i<dss;i++){
            ds3[i]=dstmp[i];
            ds3[i+dss]=dstmp[i]+N;
            ds3[i+dss+dss]=dstmp[i]+N+N;
        }
        for(int i=0;i<=dss*2;i++){
            len[i]=ds3[i+dss-1]-ds3[i];
        }
        int mi=INF,from;
        for(int i=0;i<=dss;i++){
            int now=abs(N-ds3[i])+len[i];
            if(now<=mi){
                mi=now;
                from=i;
            }
        }
        mins[0]=mi;
        int beffrom=from;
        for(int i=N+1;i<N*2;i++){
            int stllen=abs(ds3[beffrom]-i)+len[beffrom];
            int nextlen=abs(ds3[beffrom+1]-i)+len[beffrom+1];
            if(nextlen<=stllen) beffrom++;
            mins[i-N]=min(nextlen,stllen);
        }
        for(int i=0;i<N;i++){
            minmin[i]=mins[i];
        }
    }
    {
        for(int i=0;i<(int)dstmp.size();i++){
            dstmp[i]=(N-dstmp[i])%N;
        }
        sort(ALL(dstmp));
        dstmp.erase(unique(ALL(dstmp)),dstmp.end());
        int dss=dstmp.size();
        for(int i=0;i<dss;i++){
            ds3[i]=dstmp[i];
            ds3[i+dss]=dstmp[i]+N;
            ds3[i+dss+dss]=dstmp[i]+N+N;
        }
        for(int i=0;i<=dss*2;i++){
            len[i]=ds3[i+dss-1]-ds3[i];
        }
        int mi=INF,from;
        for(int i=0;i<=dss;i++){
            int now=abs(N-ds3[i])+len[i];
            if(now<=mi){
                mi=now;
                from=i;
            }
        }
        mins2[0]=mi;
        int beffrom=from;
        for(int i=N+1;i<N*2;i++){
            int stllen=abs(ds3[beffrom]-i)+len[beffrom];
            int nextlen=abs(ds3[beffrom+1]-i)+len[beffrom+1];
            if(nextlen<=stllen) beffrom++;
            mins2[i-N]=min(nextlen,stllen);
        }
        for(int i=0;i<N;i++){
            minmin[(N-i)%N]=min(minmin[(N-i)%N],mins2[i]);
        }
    }
    for(int i=0;i<N;i++){
        printf("%d\n",minmin[i]+min(i,N-i));
    }
}