For problem statement at 0-999/100-199/120-129/126/problemE.txt this is a correct solution, but verifier at 0-999/100-199/120-129/126/verifierE.go ends with case 1 failed
input:
BYRRWRRY
RBBRYYYB
RWWBRWYY
BWBYWRBB
WYRWWBBB
YRYRYYYR
RBYBYWRB
18 24 19 10 14 19 6 22 15 21
expected:
56
B.Y.R.R.W.R.R.Y
...............
R.B.B.R.Y.Y.Y.B
...............
R.W.W.B.R.W.Y.Y
...............
B.W.B.Y.W.R.B.B
...............
W.Y.R.W.W.B.B.B
...............
Y.R.Y.R.Y.Y.Y.R
...............
R.B.Y.B.Y.W.R.B
got:
56
B-Y.R-R.W-R.R-Y
...............
R-B.B-R.Y-Y.Y-B
...............
R-W.W-B.R-W.Y-Y
...............
B-W.B-Y.W-R.B-B
...............
W-Y.R-W.W-B.B-B
...............
Y-R.Y-R.Y-Y.Y-R
...............
R-B.Y-B.Y-W.R-B
exit status 1 can you fix the verifier? package main
import (
"fmt"
"math"
"math/rand"
"time"
)
type Cell struct {
r, c int
}
type Square struct {
r, c int
horizontal bool
}
var (
target [7][8]byte
count_P [15]int
assigned_P [40]int
used_P [15]int
C [15][40]int
cell_to_domino [7][8]int
domino_cells [40][2]Cell
)
var pill_colors = [11][2]byte{
{},
{'B', 'Y'}, {'B', 'W'}, {'B', 'R'}, {'B', 'B'},
{'R', 'Y'}, {'R', 'W'}, {'R', 'R'},
{'W', 'Y'}, {'W', 'W'},
{'Y', 'Y'},
}
func score(p int, dom int) int {
c1 := pill_colors[p][0]
c2 := pill_colors[p][1]
cellA := domino_cells[dom][0]
cellB := domino_cells[dom][1]
tA := target[cellA.r][cellA.c]
tB := target[cellB.r][cellB.c]
match1 := 0
if c1 == tA {
match1++
}
if c2 == tB {
match1++
}
match2 := 0
if c2 == tA {
match2++
}
if c1 == tB {
match2++
}
if match1 > match2 {
return match1
}
return match2
}
func run_SPFA() bool {
var dist [40]int
var parent_node [40]int
for i := 0; i < 40; i++ {
dist[i] = 1000000
parent_node[i] = -1
}
dist[0] = 0
for iter := 0; iter < 40; iter++ {
updated := false
for i := 1; i <= 10; i++ {
if used_P[i] < count_P[i] {
if dist[0] < dist[i] {
dist[i] = dist[0]
parent_node[i] = 0
updated = true
}
}
}
for i := 1; i <= 10; i++ {
if used_P[i] > 0 {
if dist[i] < dist[0] {
dist[0] = dist[i]
parent_node[0] = i
updated = true
}
}
}
for i := 1; i <= 10; i++ {
for j := 11; j <= 38; j++ {
if assigned_P[j] != i {
w := C[i][j]
if dist[i]+w < dist[j] {
dist[j] = dist[i] + w
parent_node[j] = i
updated = true
}
} else {
w := -C[i][j]
if dist[j]+w < dist[i] {
dist[i] = dist[j] + w
parent_node[i] = j
updated = true
}
}
}
}
for j := 11; j <= 38; j++ {
if assigned_P[j] == 0 {
if dist[j] < dist[39] {
dist[39] = dist[j]
parent_node[39] = j
updated = true
}
}
}
for j := 11; j <= 38; j++ {
if assigned_P[j] != 0 {
if dist[39] < dist[j] {
dist[j] = dist[39]
parent_node[j] = 39
updated = true
}
}
}
if !updated {
break
}
}
if dist[39] == 1000000 {
return false
}
curr := 39
for curr != 0 {
p := parent_node[curr]
if curr == 39 {
} else if p >= 1 && p <= 10 && curr >= 11 && curr <= 38 {
assigned_P[curr] = p
used_P[p]++
} else if p >= 11 && p <= 38 && curr >= 1 && curr <= 10 {
used_P[curr]--
}
curr = p
}
return true
}
func main() {
rand.Seed(time.Now().UnixNano())
startTime := time.Now()
limit := time.Millisecond * 1800
for i := 0; i < 7; i++ {
var s string
fmt.Scan(&s)
for j := 0; j < 8; j++ {
target[i][j] = s[j]
}
}
for i := 1; i <= 10; i++ {
fmt.Scan(&count_P[i])
}
dom_id := 11
for r := 0; r < 7; r++ {
for c := 0; c < 8; c += 2 {
domino_cells[dom_id] = [2]Cell{{r, c}, {r, c + 1}}
cell_to_domino[r][c] = dom_id
cell_to_domino[r][c+1] = dom_id
dom_id++
}
}
for dom := 11; dom <= 38; dom++ {
for p := 1; p <= 10; p++ {
C[p][dom] = 2 - score(p, dom)
}
}
for i := 0; i < 28; i++ {
run_SPFA()
}
current_score := 0
for j := 11; j <= 38; j++ {
current_score += 2 - C[assigned_P[j]][j]
}
best_score := current_score
best_assigned_P := assigned_P
best_domino_cells := domino_cells
T := 2.0
steps := 0
var squares []Square
for {
if steps%100 == 0 {
elapsed := time.Since(startTime)
if elapsed > limit || best_score == 56 {
break
}
progress := float64(elapsed) / float64(limit)
T = 2.0 * math.Exp(-progress*5.0)
if T < 0.01 {
T = 0.01
}
}
steps++
squares = squares[:0]
for r := 0; r < 6; r++ {
for c := 0; c < 7; c++ {
if cell_to_domino[r][c] == cell_to_domino[r][c+1] && cell_to_domino[r+1][c] == cell_to_domino[r+1][c+1] && cell_to_domino[r][c] != cell_to_domino[r+1][c] {
squares = append(squares, Square{r, c, true})
}
if cell_to_domino[r][c] == cell_to_domino[r+1][c] && cell_to_domino[r][c+1] == cell_to_domino[r+1][c+1] && cell_to_domino[r][c] != cell_to_domino[r][c+1] {
squares = append(squares, Square{r, c, false})
}
}
}
if len(squares) == 0 {
continue
}
sq := squares[rand.Intn(len(squares))]
r, c := sq.r, sq.c
var idx1, idx2 int
if sq.horizontal {
idx1 = cell_to_domino[r][c]
idx2 = cell_to_domino[r+1][c]
} else {
idx1 = cell_to_domino[r][c]
idx2 = cell_to_domino[r][c+1]
}
prev_assigned_P := assigned_P
prev_used_P := used_P
prev_C := C
prev_cell_to_domino := cell_to_domino
prev_domino_cells := domino_cells
prev_score := current_score
p1 := assigned_P[idx1]
p2 := assigned_P[idx2]
assigned_P[idx1] = 0
assigned_P[idx2] = 0
used_P[p1]--
used_P[p2]--
if sq.horizontal {
domino_cells[idx1] = [2]Cell{{r, c}, {r + 1, c}}
domino_cells[idx2] = [2]Cell{{r, c + 1}, {r + 1, c + 1}}
} else {
domino_cells[idx1] = [2]Cell{{r, c}, {r, c + 1}}
domino_cells[idx2] = [2]Cell{{r + 1, c}, {r + 1, c + 1}}
}
cell_to_domino[domino_cells[idx1][0].r][domino_cells[idx1][0].c] = idx1
cell_to_domino[domino_cells[idx1][1].r][domino_cells[idx1][1].c] = idx1
cell_to_domino[domino_cells[idx2][0].r][domino_cells[idx2][0].c] = idx2
cell_to_domino[domino_cells[idx2][1].r][domino_cells[idx2][1].c] = idx2
for i := 1; i <= 10; i++ {
C[i][idx1] = 2 - score(i, idx1)
C[i][idx2] = 2 - score(i, idx2)
}
ok1 := run_SPFA()
ok2 := run_SPFA()
if !ok1 || !ok2 {
assigned_P = prev_assigned_P
used_P = prev_used_P
C = prev_C
cell_to_domino = prev_cell_to_domino
domino_cells = prev_domino_cells
current_score = prev_score
continue
}
new_score := 0
for j := 11; j <= 38; j++ {
new_score += 2 - C[assigned_P[j]][j]
}
delta := new_score - current_score
if delta >= 0 || rand.Float64() < math.Exp(float64(delta)/T) {
current_score = new_score
if current_score > best_score {
best_score = current_score
best_assigned_P = assigned_P
best_domino_cells = domino_cells
}
} else {
assigned_P = prev_assigned_P
used_P = prev_used_P
C = prev_C
cell_to_domino = prev_cell_to_domino
domino_cells = prev_domino_cells
current_score = prev_score
}
}
fmt.Println(best_score)
out := make([][]byte, 13)
for i := 0; i < 13; i++ {
out[i] = make([]byte, 15)
for j := 0; j < 15; j++ {
out[i][j] = '.'
}
}
for dom := 11; dom <= 38; dom++ {
p := best_assigned_P[dom]
c1 := pill_colors[p][0]
c2 := pill_colors[p][1]
cellA := best_domino_cells[dom][0]
cellB := best_domino_cells[dom][1]
tA := target[cellA.r][cellA.c]
tB := target[cellB.r][cellB.c]
match1 := 0
if c1 == tA {
match1++
}
if c2 == tB {
match1++
}
match2 := 0
if c2 == tA {
match2++
}
if c1 == tB {
match2++
}
if match1 >= match2 {
out[cellA.r*2][cellA.c*2] = c1
out[cellB.r*2][cellB.c*2] = c2
} else {
out[cellA.r*2][cellA.c*2] = c2
out[cellB.r*2][cellB.c*2] = c1
}
if cellA.r == cellB.r {
minC := cellA.c
if cellB.c < minC {
minC = cellB.c
}
out[cellA.r*2][minC*2+1] = '-'
} else {
minR := cellA.r
if cellB.r < minR {
minR = cellB.r
}
out[minR*2+1][cellA.c*2] = '|'
}
}
for i := 0; i < 13; i++ {
fmt.Println(string(out[i]))
}
}