#1021622 (Go) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	ID 21712
提出日時	2024-10-21 15:33:55
言語	Go (1.22.1)
結果	AC
実行時間	763 ms / 1,000 ms
コード長	1,090 bytes
コンパイル時間	19,881 ms
コンパイル使用メモリ	244,120 KB
実行使用メモリ	8,176 KB
スコア	33,935,092
最終ジャッジ日時	2024-10-21 15:35:06
合計ジャッジ時間	51,331 ms
ジャッジサーバーID （参考情報）	judge3 / judge1
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	710 ms 8,080 KB
testcase_01	AC	734 ms 8,076 KB
testcase_02	AC	733 ms 8,076 KB
testcase_03	AC	710 ms 8,080 KB
testcase_04	AC	732 ms 8,080 KB
testcase_05	AC	712 ms 8,076 KB
testcase_06	AC	741 ms 8,080 KB
testcase_07	AC	733 ms 8,076 KB
testcase_08	AC	711 ms 8,076 KB
testcase_09	AC	736 ms 8,080 KB
testcase_10	AC	713 ms 8,080 KB
testcase_11	AC	739 ms 8,076 KB
testcase_12	AC	707 ms 8,080 KB
testcase_13	AC	731 ms 8,080 KB
testcase_14	AC	742 ms 8,076 KB
testcase_15	AC	708 ms 8,080 KB
testcase_16	AC	738 ms 8,076 KB
testcase_17	AC	708 ms 8,076 KB
testcase_18	AC	728 ms 8,080 KB
testcase_19	AC	711 ms 8,080 KB
testcase_20	AC	734 ms 8,080 KB
testcase_21	AC	732 ms 8,076 KB
testcase_22	AC	721 ms 8,080 KB
testcase_23	AC	732 ms 8,076 KB
testcase_24	AC	707 ms 8,080 KB
testcase_25	AC	735 ms 8,080 KB
testcase_26	AC	709 ms 8,080 KB
testcase_27	AC	721 ms 8,080 KB
testcase_28	AC	732 ms 8,076 KB
testcase_29	AC	708 ms 8,172 KB
testcase_30	AC	731 ms 8,080 KB
testcase_31	AC	707 ms 8,080 KB
testcase_32	AC	733 ms 8,080 KB
testcase_33	AC	712 ms 8,076 KB
testcase_34	AC	738 ms 8,080 KB
testcase_35	AC	740 ms 8,080 KB
testcase_36	AC	709 ms 8,084 KB
testcase_37	AC	741 ms 8,080 KB
testcase_38	AC	710 ms 8,076 KB
testcase_39	AC	738 ms 8,080 KB
testcase_40	AC	711 ms 8,076 KB
testcase_41	AC	736 ms 8,084 KB
testcase_42	AC	738 ms 8,080 KB
testcase_43	AC	710 ms 8,076 KB
testcase_44	AC	735 ms 8,080 KB
testcase_45	AC	715 ms 8,076 KB
testcase_46	AC	736 ms 8,076 KB
testcase_47	AC	709 ms 8,076 KB
testcase_48	AC	763 ms 8,176 KB
testcase_49	AC	733 ms 8,084 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<80000; 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

結果

テストケース

ソースコード