Submission #3237756


Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
	"strconv"
)

var sc = NewScanner(os.Stdin)

func main() {
	n := sc.ScanInt()
	tmpa := sc.ScanBigInts(n)
	tmpb := sc.ScanBigInts(n)

	var res int64
	for bit := 0; bit < 28; bit++ {
		var t int64 = 1 << uint32(bit)
		a, b := make(BigInts, n), make(BigInts, n)
		for i := range a {
			a[i], b[i] = tmpa[i]%(2*t), tmpb[i]%(2*t)
		}
		sort.Sort(b)

		c := 0
		for _, aa := range a {
			c1 := SearchBigInts(b, t-aa)
			c2 := SearchBigInts(b, 2*t-aa)
			c3 := SearchBigInts(b, 3*t-aa)
			c4 := SearchBigInts(b, 4*t-aa)
			c = (c + c2 - c1 + c4 - c3) % 2
		}

		if c == 1 {
			res |= t
		}
	}

	fmt.Println(res)
}

type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner(r io.Reader) *Scanner {
	s := &Scanner{bufio.NewScanner(r)}
	s.sc.Split(bufio.ScanWords)
	return s
}

func (s *Scanner) ScanInt() int {
	s.sc.Scan()
	i, e := strconv.Atoi(s.sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) ScanBigInt() int64 {
	s.sc.Scan()
	i, e := strconv.ParseInt(s.sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) ScanBigInts(len int) []int64 {
	a := make([]int64, len)
	for i := 0; i < len; i++ {
		a[i] = s.ScanBigInt()
	}
	return a
}

type BigInts []int64

func (a BigInts) Len() int {
	return len(a)
}

func (a BigInts) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}

func (a BigInts) Less(i, j int) bool {
	return a[i] < a[j]
}

func SearchBigInts(a []int64, x int64) int {
	return sort.Search(len(a), func(i int) bool { return a[i] >= x })
}

Submission Info

Submission Time
Task D - Two Sequences
User icewaterGreentea
Language Go (1.6)
Score 0
Code Size 1640 Byte
Status WA
Exec Time 3160 ms
Memory 18588 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 4
AC × 8
WA × 2
TLE × 6
Set Name Test Cases
Sample example_0, example_1, example_2, example_3
All N100000_0, N100000_1, N150000_0, N150000_1, N200000_0, N200000_1, N200000_ex_0, N200000_ex_1, example_0, example_1, example_2, example_3, rand_0, rand_1, smallrand_0, smallrand_1
Case Name Status Exec Time Memory
N100000_0 AC 2069 ms 7808 KB
N100000_1 WA 2068 ms 8576 KB
N150000_0 TLE 3160 ms 11136 KB
N150000_1 TLE 3156 ms 13696 KB
N200000_0 TLE 3156 ms 18588 KB
N200000_1 TLE 3156 ms 13824 KB
N200000_ex_0 TLE 3156 ms 14720 KB
N200000_ex_1 TLE 3156 ms 16384 KB
example_0 AC 1 ms 640 KB
example_1 AC 1 ms 640 KB
example_2 AC 1 ms 640 KB
example_3 AC 1 ms 640 KB
rand_0 AC 105 ms 3968 KB
rand_1 WA 231 ms 5248 KB
smallrand_0 AC 1 ms 640 KB
smallrand_1 AC 1 ms 640 KB