結果

問題 No.133 カードゲーム
ユーザー ktateish
提出日時 2020-01-21 08:52:46
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 6,573 bytes
コンパイル時間 11,032 ms
コンパイル使用メモリ 225,640 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-04 23:06:32
合計ジャッジ時間 11,877 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
    "bufio"
    "bytes"
    "fmt"
    "io"
    "os"
    "strconv"
)
// -----------------------------------------------------------------------------
// IO helper functions
// Returns next token from input.  It must be initialized by SetInput()
// before the first call.
var nextToken func() ([]byte, error)
var nextLine func() ([]byte, error)
// Holds a buffer for output.  It must be initialized by SetOutput().
// All IO fucntions (read*() and [e]print*()) should write to OutputWriter
// instead of this.
var OutputBuffer *bufio.Writer
// Holds an io.Writer.  It must be initialized by SetOutput()
var OutputWriter io.Writer
// Set IO functions for interactive input/output.
func SetInteractive(w io.Writer, r io.Reader) {
    SetUnbefferedInput(r)
    OutputBuffer = nil
    OutputWriter = w
}
// Setup OutputBuffer and OutputWriter.
func SetOutput(w io.Writer) {
    OutputBuffer = bufio.NewWriter(w)
    OutputWriter = OutputBuffer
}
// Flushes OutputBuffer
func Flush() {
    if OutputBuffer != nil {
        OutputBuffer.Flush()
    }
}
// Returns true if c is a white space
func IsSpace(c byte) bool {
    switch c {
    case '\t', '\n', '\v', '\f', '\r', ' ':
        return true
    }
    return false
}
func IsNewLine(c byte) bool {
    switch c {
    case '\n', '\r':
        return true
    }
    return false
}
// Setup nextToken with input buffer.
func SetInput(r io.Reader) {
    buf := new(bytes.Buffer)
    var b []byte
    var i int
    rest := func() ([]byte, error) {
        for i < len(b) && IsSpace(b[i]) {
            i++
        }
        if i == len(b) {
            return nil, io.ErrUnexpectedEOF
        }
        j := i
        for i < len(b) && !IsSpace(b[i]) {
            i++
        }
        return b[j:i], nil
    }
    initial := func() ([]byte, error) {
        io.Copy(buf, r)
        b = buf.Bytes()
        nextToken = rest
        return rest()
    }
    nextToken = initial
    restLn := func() ([]byte, error) {
        for i < len(b) && IsNewLine(b[i]) {
            i++
        }
        if i == len(b) {
            return nil, io.ErrUnexpectedEOF
        }
        j := i
        for i < len(b) && !IsNewLine(b[i]) {
            i++
        }
        return b[j:i], nil
    }
    initialLn := func() ([]byte, error) {
        io.Copy(buf, r)
        b = buf.Bytes()
        nextLine = restLn
        return restLn()
    }
    nextLine = initialLn
}
// Setup nextToken without input buffer.
func SetUnbefferedInput(r io.Reader) {
    buf := bufio.NewReader(r)
    var b []byte
    var i int
    nextToken = func() ([]byte, error) {
        var err error
        if i == len(b) {
            b, err = buf.ReadBytes('\n')
            if err != nil {
                return nil, err
            }
            i = 0
            j := len(b) - 1
            for 0 <= j && IsSpace(b[j]) {
                j--
            }
            b = b[0 : j+1]
        }
        for i < len(b) && IsSpace(b[i]) {
            i++
        }
        j := i
        for i < len(b) && !IsSpace(b[i]) {
            i++
        }
        if i == j {
            return nil, io.ErrUnexpectedEOF
        }
        return b[j:i], nil
    }
}
// -----------------------------------------------------------------------------
// IO functions
// Reads next token and return it as []byte
func readb() []byte {
    b, err := nextToken()
    if err != nil {
        panic(err)
    }
    return b
}
// Reads next token and return it as string
func reads() string {
    return string(readb())
}
// Read next line as []byte
func readbln() []byte {
    b, err := nextLine()
    if err != nil {
        panic(err)
    }
    return b
}
// Read next line as string
func readsln() string {
    return string(readbln())
}
// Reads next token and return it as int64
func readll() int64 {
    i, err := strconv.ParseInt(reads(), 10, 64)
    if err != nil {
        panic(err.Error())
    }
    return i
}
// Reads next token and return it as int
func readi() int {
    return int(readll())
}
// Reads next token and return it as float64
func readf() float64 {
    f, err := strconv.ParseFloat(reads(), 64)
    if err != nil {
        panic(err.Error())
    }
    return f
}
// Write args to OutputWriter with the format f
func printf(f string, args ...interface{}) (int, error) {
    return fmt.Fprintf(OutputWriter, f, args...)
}
// Write args to OutputWriter without format
func println(args ...interface{}) (int, error) {
    return fmt.Fprintln(OutputWriter, args...)
}
// Write args to stderr with the format f
func eprintf(f string, args ...interface{}) (int, error) {
    return fmt.Fprintf(os.Stderr, f, args...)
}
// Write args to stderr without format
func eprintln(args ...interface{}) (int, error) {
    return fmt.Fprintln(os.Stderr, args...)
}
// -----------------------------------------------------------------------------
// Simple math functions
const (
    // big prime
    INF  = 1000000007
    INF2 = 1000000009
    INF3 = 998244353
)
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func minll(a, b int64) int64 {
    if a < b {
        return a
    }
    return b
}
func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}
func maxll(a, b int64) int64 {
    if a < b {
        return b
    }
    return a
}
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}
func absll(a int64) int64 {
    if a < 0 {
        return -a
    }
    return a
}
// egcd(a, b) returns d, x, y:
//   d is gcd(a,b)
//   x, y are  integers that satisfy ax + by = d
func egcd(a, b int) (int, int, int) {
    if b == 0 {
        return a, 1, 0
    }
    d, x, y := egcd(b, a%b)
    return d, y, x - a/b*y
}
func egcdll(a, b int64) (int64, int64, int64) {
    if b == 0 {
        return a, 1, 0
    }
    d, x, y := egcdll(b, a%b)
    return d, y, x - a/b*y
}
func gcd(a, b int) int {
    d, _, _ := egcd(a, b)
    return d
}
func gcdll(a, b int64) int64 {
    d, _, _ := egcdll(a, b)
    return d
}
// set up IO functions
func init() {
    // for non-interactive
    SetInput(os.Stdin)
    SetOutput(os.Stdout)
    // Enable below when interactive.  Its ok to leave above intact.
    // SetInteractive(os.Stdout, os.Stdin)
}
func main() {
    defer Flush()
    N := readi()
    A := make([]int, N)
    B := make([]int, N)
    for i := range A {
        A[i] = readi()
    }
    for i := range B {
        B[i] = readi()
    }
    var win, count int
    DoPermutation0n(N, func(a []int) {
        DoPermutation0n(N, func(b []int) {
            count++
            w := 0
            for k := range a {
                i := a[k]
                j := b[k]
                if B[j] < A[i] {
                    w++
                }
            }
            if N-w < w {
                win++
            }
        })
    })
    printf("%8f\n", float64(win)/float64(count))
}
// Heap's algorithm
func DoPermutation(a []int, fn func([]int)) {
    n := len(a)
    c := make([]int, n)
    i := 0
    swap := func(i, j int) {
        a[i], a[j] = a[j], a[i]
    }
    fn(a)
    for i < n {
        if c[i] < i {
            if i%2 == 0 {
                swap(0, i)
            } else {
                swap(c[i], i)
            }
            fn(a)
            c[i]++
            i = 0
        } else {
            c[i] = 0
            i++
        }
    }
}
func DoPermutation0n(n int, fn func([]int)) {
    a := make([]int, n)
    for i := range a {
        a[i] = i
    }
    DoPermutation(a, fn)
}
func next_permutation(a []int) chan []int {
    ch := make(chan []int)
    go func() {
        DoPermutation(a, func(x []int) {
            ch <- x
        })
        close(ch)
    }()
    return ch
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0