結果
問題 | No.990 N×Mマス計算(Kの倍数) |
ユーザー | neko_the_shadow |
提出日時 | 2020-02-19 16:55:12 |
言語 | Go (1.22.1) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,390 bytes |
コンパイル時間 | 11,850 ms |
コンパイル使用メモリ | 224,204 KB |
実行使用メモリ | 12,748 KB |
最終ジャッジ日時 | 2024-11-16 03:04:29 |
合計ジャッジ時間 | 17,764 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,820 KB |
testcase_02 | AC | 1 ms
6,820 KB |
testcase_03 | AC | 1 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 1 ms
6,816 KB |
testcase_06 | AC | 1 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,820 KB |
testcase_08 | AC | 1 ms
6,816 KB |
testcase_09 | AC | 1 ms
6,820 KB |
testcase_10 | AC | 19 ms
7,636 KB |
testcase_11 | AC | 22 ms
7,624 KB |
testcase_12 | TLE | - |
testcase_13 | AC | 17 ms
7,508 KB |
testcase_14 | AC | 31 ms
7,636 KB |
testcase_15 | AC | 19 ms
7,504 KB |
testcase_16 | AC | 31 ms
8,528 KB |
testcase_17 | AC | 14 ms
6,820 KB |
testcase_18 | TLE | - |
testcase_19 | AC | 395 ms
7,632 KB |
testcase_20 | AC | 62 ms
12,748 KB |
ソースコード
package main import ( "bufio" "fmt" "math" "os" "strconv" ) func exec(stdin *Stdin, stdout *Stdout) { n := stdin.ReadInt() m := stdin.ReadInt() k := stdin.ReadInt() op := stdin.Read() a := []int{} b := []int{} for i := 0; i < m; i++ { b = append(b, stdin.ReadInt()) } for i := 0; i < n; i++ { a = append(a, stdin.ReadInt()) } ans := 0 if op == "+" { c := NewCounter() for i := 0; i < n; i++ { c.Increment(a[i] % k) } for i := 0; i < m; i++ { mod := b[i] % k if mod == 0 { ans += c.Get(0) } else { ans += c.Get(k - mod) } } } else { c := NewCounter() for i := 0; i < n; i++ { c.Increment(Gcd(k, a[i])) } gcds2 := []int{} for _, key := range c.Keys() { gcd2, _ := key.(int) gcds2 = append(gcds2, gcd2) } for i := 0; i < m; i++ { gcd1 := Gcd(k, b[i]) for _, gcd2 := range gcds2 { if (gcd1*gcd2)%k == 0 { ans += c.Get(gcd2) } } } } stdout.Println(ans) } func Gcd(x, y int) int { if x < y { x, y = y, x } for y > 0 { x, y = y, x%y } return x } func main() { stdout := NewStdout() defer stdout.Flush() exec(NewStdin(bufio.ScanWords), stdout) } type Stdin struct { stdin *bufio.Scanner } func NewStdin(split bufio.SplitFunc) *Stdin { s := Stdin{bufio.NewScanner(os.Stdin)} s.stdin.Split(split) s.stdin.Buffer(make([]byte, bufio.MaxScanTokenSize), int(math.MaxInt32)) return &s } func (s *Stdin) Read() string { s.stdin.Scan() return s.stdin.Text() } func (s *Stdin) ReadInt() int { n, _ := strconv.Atoi(s.Read()) return n } func (s *Stdin) ReadFloat64() float64 { n, _ := strconv.ParseFloat(s.Read(), 64) return n } type Stdout struct { stdout *bufio.Writer } func NewStdout() *Stdout { return &Stdout{bufio.NewWriter(os.Stdout)} } func (s *Stdout) Flush() { s.stdout.Flush() } func (s *Stdout) Println(a ...interface{}) { fmt.Fprintln(s.stdout, a...) } type Counter map[interface{}]int func NewCounter() *Counter { return &Counter{} } func (c *Counter) Increment(key interface{}) { d := map[interface{}]int(*c) d[key] = c.Get(key) + 1 } func (c *Counter) Get(key interface{}) int { d := map[interface{}]int(*c) if v, ok := d[key]; ok { return v } else { return 0 } } func (c *Counter) Keys() []interface{} { d := map[interface{}]int(*c) keys := []interface{}{} for key := range d { keys = append(keys, key) } return keys }