Submission #1186675

---

Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func NewIo() *Io {
	return &Io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *Io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *Io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (io *Io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

func (io *Io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) PrintLn(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *Io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

func (io *Io) PrintIntLn(a []int) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func (io *Io) PrintStringLn(a []string) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func Log(name string, value interface{}) {
	fmt.Fprintf(os.Stderr, "%s=%+v\n", name, value)
}

func intMin(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func intMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// argument: X
// min [0, k) < X となる最小のkを返す関数を作る
const (
	sqrtN = 512
	INF   = 1000000000
)

type SqrtDecomposition struct {
	N        int
	K        int
	data     []int
	blockMin []int
}

func NewSqrtDecomposition(n int) *SqrtDecomposition {
	k := (n + sqrtN - 1) / sqrtN
	sq := &SqrtDecomposition{
		N:        n,
		K:        k,
		data:     make([]int, k*sqrtN),
		blockMin: make([]int, k),
	}
	for i := 0; i < len(sq.data); i++ {
		sq.data[i] = -1
	}
	for i := 0; i < len(sq.blockMin); i++ {
		sq.blockMin[i] = -1
	}
	return sq
}

func (sq *SqrtDecomposition) Update(x, y int) {
	k := x / sqrtN
	sq.data[x] = y
	minval := INF
	for i := k * sqrtN; i < (k+1)*sqrtN; i++ {
		minval = intMin(minval, sq.data[i])
	}
	sq.blockMin[k] = minval
}

func (sq *SqrtDecomposition) Find(x int) int {
	for k := 0; k < sq.K; k++ {
		if sq.blockMin[k] < x {
			for i := k * sqrtN; i < (k+1)*sqrtN; i++ {
				if sq.data[i] < x {
					return i
				}
			}
		}
	}
	return -1
}

func main() {
	io := NewIo()
	defer io.Flush()
	N := io.NextInt()
	C := make([]int, N)
	A := make([]int, N)
	for i := 1; i < N; i++ {
		C[i] = io.NextInt()
		A[i] = io.NextInt()
	}
	grundy := make([]int, N)
	grundy[0] = 0
	//index := make([]int, N)
	//index[0] = 0
	//for i := 1; i < N; i++ {
	//	index[i] = -1
	//}
	//for i := 1; i < N; i++ {
	//	for k := 0; k < N; k++ {
	//		if i - C[i] <= index[k] {
	//			// do nothing
	//		} else {
	//			grundy[i] = k
	//			break
	//		}
	//	}
	//	index[grundy[i]] = i
	//}
	sq := NewSqrtDecomposition(N)
	sq.Update(0, 0)
	for i := 1; i < N; i++ {
		grundy[i] = sq.Find(i - C[i])
		//Log("grundy[i]", grundy[i])
		sq.Update(grundy[i], i)
	}
	//Log("C", C)
	//Log("grundy", grundy)
	xor := 0
	for i := 0; i < N; i++ {
		if A[i]%2 == 1 {
			xor = xor ^ grundy[i]
		}
	}
	if xor == 0 {
		io.PrintLn("Second")
	} else {
		io.PrintLn("First")
	}
}

Submission Info

Judge Result