問題はこちら
No.326 あみだますたー - yukicoder
{1,…,N}上の順序 "<" を i < j ⇔ Ai < Aj により定める
このとき、「あみだくじによって数列{Ai}を作ること」と「順序"<"によってバブルソートをすること」が対応する
(完成するあみだくじにおいて左にある数ほど"小さい"と考えるということ)
ということでバブルソートを実装するだけ
d[110],g[110],ans[6000];c,i,j,n,k,t,a,b;
main(){
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)d[i]=i;
while(k--){
scanf("%d%d",&a,&b);
d[a]^=d[b]^=d[a]^=d[b];
}
for(i=1;i<=n;i++)scanf("%d",g+i);
for(i=1;i<=n;i++)for(j=1;j<=n-i;j++)if(g[d[j]]>g[d[j+1]]){
ans[c++]=j;
d[j]^=d[j+1]^=d[j]^=d[j+1];
}
printf("%d\n",c);
for(i=0;i<c;i++)printf("%d %d\n",ans[i],ans[i]+1);
}
さてこれを縮めよう
この問題はスペシャルジャッジなので、出力を全て空白区切りで行っても大丈夫であることを利用してprintfを1つにまとめることができる
また大量にある変数たちもぐっと睨むことでいくつか減らすことが出来る
とりあえずこう
d[110],g[110],s[6000];c,i,j;
main(n,k,a,b){
for(scanf("%d%d",&n,&k);i++<n;)d[i]=i;
for(;k--;d[a]^=d[b]^=d[a]^=d[b])scanf("%d%d",&a,&b);
for(;~scanf("%d",++j+g););
for(;n--;)for(i=0;i++<n;)g[d[i]]>g[d[i+1]]?d[s[c++]=i]^=d[i+1]^=d[i]^=d[i+1]:0;
for(;k<c*2;k++)printf("%d ",~k?s[k/2]+k%2:c);
}
for文をまとめていく
前の方に出てくる変数を後ろの方でうっかりいじらないように注意する
また、3つ目のfor文に出てくるjのincを上手く使って、それ以降のループを調整する
for(scanf("%d%d",&n,&k);i++<n;)d[i]=i;for(;k--;d[a]^=d[b]^=d[a]^=d[b])scanf("%d%d",&a,&b);
for(scanf("%d%d",&n,&k);i++<n?d[i]=i:k--?scanf("%d%d",&a,&b),d[a]^=d[b]^=d[a]^=d[b]:0;);
for(;i++<105?d[i]=i:k--?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):0;);
for(;i++<105?d[i]=i:k--?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):0;);for(;~scanf("%d",++j+g););
for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g););
for(;n--;)for(i=0;i++<n;)g[d[i]]>g[d[i+1]]?d[s[c++]=i]^=d[i+1]^=d[i]^=d[i+1]:0;
for(;j++<n?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:(j=0,n--););
for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g););for(;j++<n?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:(j=0,n--););
for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g)?:n/j?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:(j=0,n--););
for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g)?:n/j?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:(j=0,n--););for(;k<c*2;k++)printf("%d ",~k?s[k/2]+k%2:c);
for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g)?:n/j?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:n?j=!n--,1:printf("%d ",j-1?s[j/2]+j%2:c)&&j-2*c-1;);
for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g)?:n/j?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:n?j=!n--,1:j-2*c-!!printf("%d ",j-1?s[j/2]+j%2:c););
というわけで完成したものがこれ
d[110],g[110],s[6000];c,i,j,n;
main(k,a,b){
for(;i++<105?d[i]=i:
k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):
~scanf("%d",++j+g)?:
n/j?g[d[j]]>g[d[j+1]]?d[s[++c]=j]^=d[j+1]^=d[j]^=d[j+1]:1:
n?j=!n--,1:
j-2*c-!!printf("%d ",j-1?s[j/2]+j%2:c);
);
}
254B