For problem statement at 2000-2999/2100-2199/2140-2149/2141/problemG.txt this is a correct solution, but verifier at 2000-2999/2100-2199/2140-2149/2141/verifierG.go ends with mismatch on test 6: expected 12, got 14
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
var t int
fmt.Fscan(reader, &t)
for i := 0; i < t; i++ {
var n int
fmt.Fscan(reader, &n)
pts := make([]point, n)
for j := 0; j < n; j++ {
fmt.Fscan(reader, &pts[j].x, &pts[j].y)
pts[j].id = j
}
fmt.Fprintln(writer, solve(pts))
}
}
type point struct {
x, y, id int
}
func solve(pts []point) int64 {
n := len(pts)
if n == 0 {
return 0
}
ptsX := make([]point, n)
copy(ptsX, pts)
sortPointsByX(ptsX)
ptsY := make([]point, n)
copy(ptsY, pts)
sortPointsByY(ptsY)
ptsXY := make([]point, n)
copy(ptsXY, pts)
sortPointsByXY(ptsXY)
ptsYX := make([]point, n)
copy(ptsYX, pts)
sortPointsByYX(ptsYX)
right := make([]int, n)
up := make([]int, n)
for i := 0; i < n; i++ {
right[i] = -1
up[i] = -1
}
for i := 0; i < n-1; i++ {
if ptsY[i].y == ptsY[i+1].y && ptsY[i].x+1 == ptsY[i+1].x {
right[ptsY[i].id] = ptsY[i+1].id
}
}
for i := 0; i < n-1; i++ {
if ptsX[i].x == ptsX[i+1].x && ptsX[i].y+1 == ptsX[i+1].y {
up[ptsX[i].id] = ptsX[i+1].id
}
}
L := make([]int, n)
R := make([]int, n)
D := make([]int, n)
U := make([]int, n)
LU := make([]int, n)
LD := make([]int, n)
RU := make([]int, n)
RD := make([]int, n)
for i := 0; i < n; i++ {
u := ptsY[i].id
L[u] = 1
D[u] = 1
LD[u] = 1
if i > 0 && ptsY[i].y == ptsY[i-1].y && ptsY[i].x == ptsY[i-1].x+1 {
v := ptsY[i-1].id
L[u] += L[v]
if up[v] != -1 {
LD[u] = LD[v] + 1
}
}
}
for i := n - 1; i >= 0; i-- {
u := ptsY[i].id
R[u] = 1
U[u] = 1
RU[u] = 1
if i < n-1 && ptsY[i].y == ptsY[i+1].y && ptsY[i].x+1 == ptsY[i+1].x {
v := ptsY[i+1].id
R[u] += R[v]
if up[v] != -1 {
RU[u] = RU[v] + 1
}
}
}
for i := 0; i < n; i++ {
u := ptsX[i].id
D[u] = 1
RD[u] = 1
if i > 0 && ptsX[i].x == ptsX[i-1].x && ptsX[i].y == ptsX[i-1].y+1 {
v := ptsX[i-1].id
D[u] += D[v]
if right[v] != -1 {
RD[u] = RD[v] + 1
}
}
}
for i := n - 1; i >= 0; i-- {
u := ptsX[i].id
U[u] = 1
LU[u] = 1
if i < n-1 && ptsX[i].x == ptsX[i+1].x && ptsX[i].y+1 == ptsX[i+1].y {
v := ptsX[i+1].id
U[u] += U[v]
if right[v] != -1 {
LU[u] = LU[v] + 1
}
}
}
for i := 0; i < n; i++ {
u := ptsXY[i].id
if right[u] != -1 && up[u] != -1 && right[up[u]] != -1 {
RU[u] = RU[right[up[u]]] + 1
}
}
for i := 0; i < n; i++ {
u := ptsYX[i].id
if right[u] != -1 && up[u] != -1 && right[up[u]] != -1 {
LU[right[u]] = LU[up[u]] + 1
}
}
for i := n - 1; i >= 0; i-- {
u := ptsXY[i].id
if right[u] != -1 && up[u] != -1 && right[up[u]] != -1 {
LD[up[right[u]]] = LD[u] + 1
}
}
for i := n - 1; i >= 0; i-- {
u := ptsYX[i].id
if right[u] != -1 && up[u] != -1 && right[up[u]] != -1 {
RD[up[u]] = RD[right[u]] + 1
}
}
var ans int64
for i := 0; i < n; i++ {
ans += int64(R[i] + U[i] + L[i] + D[i] + RU[i] + LU[i] + RD[i] + LD[i] - 8)
}
return ans
}
func sortPointsByX(a []point) {
if len(a) < 2 {
return
}
mid := len(a) / 2
sortPointsByX(a[:mid])
sortPointsByX(a[mid:])
mergeByX(a, mid)
}
func mergeByX(a []point, mid int) {
left := make([]point, mid)
copy(left, a[:mid])
right := make([]point, len(a)-mid)
copy(right, a[mid:])
i, j, k := 0, 0, 0
for i < len(left) && j < len(right) {
if left[i].x < right[j].x || (left[i].x == right[j].x && left[i].y < right[j].y) {
a[k] = left[i]
i++
} else {
a[k] = right[j]
j++
}
k++
}
for i < len(left) {
a[k] = left[i]
i++
k++
}
for j < len(right) {
a[k] = right[j]
j++
k++
}
}
func sortPointsByY(a []point) {
if len(a) < 2 {
return
}
mid := len(a) / 2
sortPointsByY(a[:mid])
sortPointsByY(a[mid:])
mergeByY(a, mid)
}
func mergeByY(a []point, mid int) {
left := make([]point, mid)
copy(left, a[:mid])
right := make([]point, len(a)-mid)
copy(right, a[mid:])
i, j, k := 0, 0, 0
for i < len(left) && j < len(right) {
if left[i].y < right[j].y || (left[i].y == right[j].y && left[i].x < right[j].x) {
a[k] = left[i]
i++
} else {
a[k] = right[j]
j++
}
k++
}
for i < len(left) {
a[k] = left[i]
i++
k++
}
for j < len(right) {
a[k] = right[j]
j++
k++
}
}
func sortPointsByXY(a []point) {
if len(a) < 2 {
return
}
mid := len(a) / 2
sortPointsByXY(a[:mid])
sortPointsByXY(a[mid:])
mergeByXY(a, mid)
}
func mergeByXY(a []point, mid int) {
left := make([]point, mid)
copy(left, a[:mid])
right := make([]point, len(a)-mid)
copy(right, a[mid:])
i, j, k := 0, 0, 0
for i < len(left) && j < len(right) {
if left[i].x+left[i].y < right[j].x+right[j].y || (left[i].x+left[i].y == right[j].x+right[j].y && left[i].x < right[j].x) {
a[k] = left[i]
i++
} else {
a[k] = right[j]
j++
}
k++
}
for i < len(left) {
a[k] = left[i]
i++
k++
}
for j < len(right) {
a[k] = right[j]
j++
k++
}
}
func sortPointsByYX(a []point) {
if len(a) < 2 {
return
}
mid := len(a) / 2
sortPointsByYX(a[:mid])
sortPointsByYX(a[mid:])
mergeByYX(a, mid)
}
func mergeByYX(a []point, mid int) {
left := make([]point, mid)
copy(left, a[:mid])
right := make([]point, len(a)-mid)
copy(right, a[mid:])
i, j, k := 0, 0, 0
for i < len(left) && j < len(right) {
if left[i].y-left[i].x < right[j].y-right[j].x || (left[i].y-left[i].x == right[j].y-right[j].x && left[i].y < right[j].y) {
a[k] = left[i]
i++
} else {
a[k] = right[j]
j++
}
k++
}
for i < len(left) {
a[k] = left[i]
i++
k++
}
for j < len(right) {
a[k] = right[j]
j++
k++
}
}