#1021634 (Go) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: ID 21712
• 提出日時: 2024-10-21 16:17:27
• 言語: Go (1.22.1)
• 結果: AC
• 実行時間: 611 ms / 1,000 ms
• コード長: 1,085 bytes
• コンパイル時間: 11,431 ms
• コンパイル使用メモリ: 221,376 KB
• 実行使用メモリ: 8,084 KB
• スコア: 32,630,832
• 最終ジャッジ日時: 2024-10-21 16:18:12
• 合計ジャッジ時間: 44,080 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	575 ms; 8,080 KB
testcase_01	AC	601 ms; 8,076 KB
testcase_02	AC	579 ms; 8,080 KB
testcase_03	AC	600 ms; 8,076 KB
testcase_04	AC	577 ms; 8,076 KB
testcase_05	AC	607 ms; 8,076 KB
testcase_06	AC	581 ms; 8,076 KB
testcase_07	AC	603 ms; 8,080 KB
testcase_08	AC	579 ms; 8,076 KB
testcase_09	AC	599 ms; 8,080 KB
testcase_10	AC	582 ms; 8,076 KB
testcase_11	AC	607 ms; 8,080 KB
testcase_12	AC	583 ms; 8,076 KB
testcase_13	AC	588 ms; 8,076 KB
testcase_14	AC	579 ms; 8,080 KB
testcase_15	AC	583 ms; 8,080 KB
testcase_16	AC	611 ms; 8,080 KB
testcase_17	AC	580 ms; 8,076 KB
testcase_18	AC	605 ms; 8,076 KB
testcase_19	AC	582 ms; 8,080 KB
testcase_20	AC	608 ms; 8,080 KB
testcase_21	AC	583 ms; 8,076 KB
testcase_22	AC	609 ms; 8,080 KB
testcase_23	AC	584 ms; 8,080 KB
testcase_24	AC	607 ms; 8,080 KB
testcase_25	AC	582 ms; 8,080 KB
testcase_26	AC	591 ms; 8,080 KB
testcase_27	AC	584 ms; 8,080 KB
testcase_28	AC	592 ms; 8,080 KB
testcase_29	AC	583 ms; 8,080 KB
testcase_30	AC	583 ms; 8,076 KB
testcase_31	AC	593 ms; 8,076 KB
testcase_32	AC	582 ms; 8,076 KB
testcase_33	AC	590 ms; 8,076 KB
testcase_34	AC	583 ms; 8,076 KB
testcase_35	AC	598 ms; 8,080 KB
testcase_36	AC	584 ms; 8,080 KB
testcase_37	AC	588 ms; 8,084 KB
testcase_38	AC	583 ms; 8,076 KB
testcase_39	AC	589 ms; 8,076 KB
testcase_40	AC	581 ms; 8,076 KB
testcase_41	AC	610 ms; 8,076 KB
testcase_42	AC	581 ms; 8,076 KB
testcase_43	AC	606 ms; 8,076 KB
testcase_44	AC	586 ms; 8,076 KB
testcase_45	AC	585 ms; 8,076 KB
testcase_46	AC	596 ms; 8,080 KB
testcase_47	AC	581 ms; 8,076 KB
testcase_48	AC	606 ms; 8,076 KB
testcase_49	AC	583 ms; 8,076 KB

ソースコード

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;p++ {
			for q:=1;q<n;q++ {
				aa:=(ta[p]+ta[0])/2
				bb:=(tb[p]+tb[0])/2
				aa=(ta[q]+aa)/2
				bb=(tb[q]+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]=0,zp
			tu[49],tv[49]=0,zq
			best,u,v=zs,tu,tv
		}
	}
	
	Println(len(u))
	for i,ui:=range u {
		Println(ui+1,v[i]+1)
	}
}