#1021621 (Go) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	ID 21712
提出日時	2024-10-21 15:23:14
言語	Go (1.22.1)
結果	AC
実行時間	392 ms / 1,000 ms
コード長	1,090 bytes
コンパイル時間	13,091 ms
コンパイル使用メモリ	231,448 KB
実行使用メモリ	8,084 KB
スコア	33,027,507
最終ジャッジ日時	2024-10-21 15:23:49
合計ジャッジ時間	32,823 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	372 ms 8,076 KB
testcase_01	AC	360 ms 8,076 KB
testcase_02	AC	360 ms 8,080 KB
testcase_03	AC	371 ms 8,076 KB
testcase_04	AC	361 ms 8,076 KB
testcase_05	AC	355 ms 8,076 KB
testcase_06	AC	355 ms 8,076 KB
testcase_07	AC	363 ms 8,080 KB
testcase_08	AC	355 ms 8,080 KB
testcase_09	AC	354 ms 8,080 KB
testcase_10	AC	373 ms 8,076 KB
testcase_11	AC	355 ms 8,076 KB
testcase_12	AC	356 ms 8,076 KB
testcase_13	AC	376 ms 8,076 KB
testcase_14	AC	358 ms 8,080 KB
testcase_15	AC	355 ms 8,084 KB
testcase_16	AC	356 ms 8,080 KB
testcase_17	AC	380 ms 8,080 KB
testcase_18	AC	355 ms 8,080 KB
testcase_19	AC	356 ms 8,076 KB
testcase_20	AC	382 ms 8,076 KB
testcase_21	AC	357 ms 8,076 KB
testcase_22	AC	357 ms 8,076 KB
testcase_23	AC	381 ms 8,076 KB
testcase_24	AC	354 ms 8,080 KB
testcase_25	AC	374 ms 8,084 KB
testcase_26	AC	356 ms 8,080 KB
testcase_27	AC	373 ms 8,076 KB
testcase_28	AC	356 ms 8,080 KB
testcase_29	AC	356 ms 8,080 KB
testcase_30	AC	382 ms 8,076 KB
testcase_31	AC	355 ms 8,076 KB
testcase_32	AC	356 ms 8,080 KB
testcase_33	AC	365 ms 8,076 KB
testcase_34	AC	358 ms 8,080 KB
testcase_35	AC	356 ms 8,076 KB
testcase_36	AC	356 ms 8,076 KB
testcase_37	AC	364 ms 8,080 KB
testcase_38	AC	355 ms 8,076 KB
testcase_39	AC	392 ms 8,080 KB
testcase_40	AC	371 ms 8,076 KB
testcase_41	AC	357 ms 8,080 KB
testcase_42	AC	358 ms 8,076 KB
testcase_43	AC	376 ms 8,076 KB
testcase_44	AC	355 ms 8,076 KB
testcase_45	AC	368 ms 8,076 KB
testcase_46	AC	357 ms 8,076 KB
testcase_47	AC	373 ms 8,076 KB
testcase_48	AC	357 ms 8,080 KB
testcase_49	AC	385 ms 8,076 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package main

import . "fmt"
import "math/rand"

const X=5e17

func abs(a int64) int64 {
	if a<0 {
		return -a
	}
	return a
}

func max(a,b int64) int64 {
	if a<b {
		return b
	}
	return a
}

func main() {
	var n int
	Scan(&n)
	a:=make([]int64,n,n)
	b:=make([]int64,n,n)
	for i:=range a {
		Scan(&a[i],&b[i])
	}
	var u,v []int
	var best int64 = X+X
	
	ta:=make([]int64,n,n)
	tb:=make([]int64,n,n)
	for lp:=0; lp<40000; lp++ {
		copy(ta,a)
		copy(tb,b)
		tu:=make([]int,50,50)
		tv:=make([]int,50,50)
		for i:=0;i<48;i++ {
			p:=rand.Intn(n)
			q:=(p+rand.Intn(n-1)+1)%n
			tu[i],tv[i]=p,q
			aa:=(ta[p]+ta[q])/2
			bb:=(tb[p]+tb[q])/2
			ta[p],tb[p]=aa,bb
			ta[q],tb[q]=aa,bb
		}
		zs:=int64(X+X)
		zp,zq:=-1,-1
		for p:=1;p<n-1;p++ {
			for q:=p+1;q<n;q++ {
				aa:=(ta[p]+ta[q])/2
				bb:=(tb[p]+tb[q])/2
				aa=(ta[0]+aa)/2
				bb=(tb[0]+bb)/2
				s:=max(abs(aa-X),abs(bb-X))
				if s<zs {
					zs,zp,zq=s,p,q
				}
			}
		}
		if zs>0&&zs<best {
			tu[48],tv[48]=zp,zq
			tu[49],tv[49]=0,zp
			best,u,v=zs,tu,tv
		}
	}
	
	Println(len(u))
	for i,ui:=range u {
		Println(ui+1,v[i]+1)
	}
}

yukicoder

結果

テストケース

ソースコード