問題はこちら
No.397 NO MORE KADOMATSU - yukicoder
ソートするだけ
int main(){ int n,i,j,s,a[110],b[5000]={}; for(scanf("%d",&n);i<n;i++)scanf("%d",a+i); for(i=0;i<n;i++)for(j=1;j<n;j++)if(a[j-1]>a[j]){ b[s++]=j; a[j]^=a[j-1]^=a[j]^=a[j-1]; } printf("%d\n",s); for(i=0;i<s;i++){ printf("%d %d\n",b[i]-1,b[i]); fflush(0); } return 0; }
最後のDammy入力を先に受け取ってしまうと何故かTLEになるので、入力時に個数をちゃんと数える必要がある
するととりあえずこうなる。REにはならないらしい
a[110],s,i,k,b[5000]; main(j){ for(;*a-~i;)scanf("%d",a-i--); for(;++i;)for(j=1;a[++j];)a[j-1]>a[j]?a[j]^=a[j-1]^=a[j]^=a[j-1],b[s++]=j:0; for(printf("%d\n",s);b[i];)fflush(!printf("%d %d\n",b[i++]-2,b[i]-1)); }
出力が2つあるのがダメそう。sを*bに保存することにして出力をまとめたい
ついでに真ん中のfor文を圧縮して
a[110],i,b[5000]; main(j){ for(;*a-~i;)scanf("%d",a-i--); for(;a[++j]?a[j-1]>a[j]?a[j]^=a[j-1]^=a[j]^=a[j-1],b[++*b]=j:1:(j=1,++i);); for(;b[i];)fflush(!printf("%d %d\n"+!i++*3,b[i]-!!i*2,b[i]-1)); }
出力部分がやっぱり長い。bに保存する値を1ずらせば b[i]-!!i*2,b[i]-1 が b[i]-!!i,b[i] になって縮む
a[110],i,b[5000]; main(j){ for(;*a-~i;)scanf("%d",a-i--); for(;a[++j]?a[j-1]>a[j]?a[j]^=a[j-1]^=a[j]^=a[b[++*b]=j-1]:1:(j=1,++i);); for(;b[i];)fflush(!printf("%d %d\n"+!i++*3,b[i]-!!i,b[i])); }
2つ目と3つ目のfor文をどうにかして合体させたい
2つ目のfor文の終了条件にiを使って、3つ目ではiを使いまわしているので、変数を新たに用意する必要がありそう?
……いや、2つ目ではi<0で3つ目ではi≧0だからこれで分岐できる
a['~~'],i,b[5000]; main(j){ for(;*a-~i;)scanf("%d",a-i--); for(;a[++j]?a[j-1]>a[j]?a[j]^=a[j-1]^=a[j]^=a[b[++*b]=j-1]:1: ++i<0?j=1:b[i]&&!fflush(!printf("%d %d\n"+!i*3,b[i]-!!i,b[i]));); }
iのincがまとめられて短くなったが、a[++j]が毎回評価されるせいで、aの配列サイズを大きく取っておかないとREになってしまう。ぐぬぬ
じゃあいっそ、毎回j=1を実行することにすればいいのでは…?
++i<0?j=1:b[i]&&!fflush(!printf("%d %d\n"+!i*3,b[i]-!!i,b[i])) j=++i<0?:b[i]&&!fflush(!printf("%d %d\n"+!i*3,b[i]-!!i,b[i]))
として1B削減、と言いたいところだが、代入が三項演算子の後ろに来てしまっているので前後を入れ替える必要がありここでは短縮にならない
aの配列サイズが元通りで良くなって1B短縮
a[110],i,b[5000]; main(j){ for(;*a-~i;)scanf("%d",a-i--); for(;!a[++j]?j=++i<0?:b[i]&&!fflush(!printf("%d %d\n"+!i*3,b[i]-!!i,b[i])): a[j-1]>a[j]?a[j]^=a[j-1]^=a[j]^=a[b[++*b]=j-1]:1;); }
182B