For problem statement at 0-999/200-299/240-249/241/problemD.txt this is a correct solution, but verifier at 0-999/200-299/240-249/241/verifierD.go ends with case 28 failed
expected: Yes
4
1 2 4 5
got: Yes
3
2 3 5
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
)
type Basis struct {
val [16]int
mask [16]uint32
item [16]int
cnt int
}
func (b *Basis) QueryMask(target int) ([]int, bool) {
if target == 0 {
return []int{}, true
}
v := target
var m uint32
for bit := 15; bit >= 0; bit-- {
if ((v >> bit) & 1) == 0 {
continue
}
if b.val[bit] == 0 {
return nil, false
}
v ^= b.val[bit]
m ^= b.mask[bit]
}
res := make([]int, 0, 17)
for i := 0; i < b.cnt; i++ {
if ((m >> i) & 1) != 0 {
res = append(res, b.item[i])
}
}
return res, true
}
func (b *Basis) Insert(v int, itemIdx int) {
cur := v
var m uint32
for bit := 15; bit >= 0; bit-- {
if ((cur >> bit) & 1) == 0 {
continue
}
if b.val[bit] != 0 {
cur ^= b.val[bit]
m ^= b.mask[bit]
} else {
b.val[bit] = cur
b.mask[bit] = m ^ (1 << b.cnt)
b.item[b.cnt] = itemIdx
b.cnt++
return
}
}
}
type Interval struct {
l, r int
}
var n, p int
var a []int
var pos []int
var dig []int
var pow10d [6]int
func digitLen(x int) int {
if x < 10 {
return 1
}
if x < 100 {
return 2
}
if x < 1000 {
return 3
}
if x < 10000 {
return 4
}
return 5
}
func powMod(a, e, mod int) int {
res := 1 % mod
x := a % mod
for e > 0 {
if e&1 == 1 {
res = int(int64(res) * int64(x) % int64(mod))
}
x = int(int64(x) * int64(x) % int64(mod))
e >>= 1
}
return res
}
func sortSmall(x []int) {
for i := 1; i < len(x); i++ {
v := x[i]
j := i - 1
for j >= 0 && x[j] > v {
x[j+1] = x[j]
j--
}
x[j+1] = v
}
}
func printAns(w *bufio.Writer, ans []int) {
fmt.Fprintln(w, "Yes")
fmt.Fprintln(w, len(ans))
for i, v := range ans {
if i > 0 {
fmt.Fprint(w, " ")
}
fmt.Fprint(w, v)
}
fmt.Fprintln(w)
}
func bruteForce() []int {
limit := uint64(1) << uint(n)
for mask := uint64(1); mask < limit; mask++ {
xr := 0
rem := 0
res := make([]int, 0, n)
for i := 0; i < n; i++ {
if ((mask >> uint(i)) & 1) != 0 {
v := a[i+1]
xr ^= v
rem = int((int64(rem)*int64(pow10d[dig[v]]) + int64(v)) % int64(p))
res = append(res, i+1)
}
}
if xr == 0 && rem == 0 {
return res
}
}
return nil
}
func solveSpecial25() []int {
var b Basis
for i := 1; i <= n; i++ {
if a[i]%p == 0 {
if sub, ok := b.QueryMask(a[i]); ok {
ans := append(sub, i)
sortSmall(ans)
return ans
}
}
b.Insert(a[i], i)
}
return nil
}
func zeroXorSubset(items []int) []int {
var b Basis
for i, v := range items {
if v == 0 {
return []int{i}
}
if sub, ok := b.QueryMask(v); ok {
res := append(sub, i)
sortSmall(res)
return res
}
b.Insert(v, i)
}
return nil
}
func solveMultiples() []int {
vals := make([]int, 0)
idxs := make([]int, 0)
for i := 1; i <= n; i++ {
if a[i]%p == 0 {
vals = append(vals, a[i])
idxs = append(idxs, i)
}
}
sub := zeroXorSubset(vals)
if sub == nil {
return nil
}
ans := make([]int, 0, len(sub))
for _, id := range sub {
ans = append(ans, idxs[id])
}
sortSmall(ans)
return ans
}
func repeatedPair(states, px, seqPos []int) []int {
m := len(px) - 1
mp := make(map[uint64]int, m+1)
mp[uint64(states[0])<<16|uint64(px[0])] = 0
for i := 1; i <= m; i++ {
key := uint64(states[i])<<16 | uint64(px[i])
if prev, ok := mp[key]; ok {
ans := make([]int, 0, i-prev)
for j := prev + 1; j <= i; j++ {
ans = append(ans, seqPos[j])
}
return ans
}
if _, ok := mp[key]; !ok {
mp[key] = i
}
}
return nil
}
func scheduleGreedy(states, px, seqPos []int, policy int) []int {
m := len(px) - 1
if m == 0 {
return nil
}
next := make([]int, m)
last := make([]int, p)
for i := 0; i < p; i++ {
last[i] = -1
}
for i := m; i >= 0; i-- {
s := states[i]
if i < m {
next[i] = last[s]
}
last[s] = i
}
buckets := make([][]int, m+1)
for i := 0; i < m; i++ {
if next[i] != -1 {
buckets[next[i]] = append(buckets[next[i]], i+1)
}
}
selected := make([]Interval, 0)
var b Basis
lastEnd := 0
for end := 1; end <= m; end++ {
starts := buckets[end]
if len(starts) == 0 {
continue
}
chosenStart := 0
chosenLabel := 0
if policy == 1 {
chosenStart = -1
}
for _, start := range starts {
if start <= lastEnd {
continue
}
label := px[end] ^ px[start-1]
if label == 0 {
ans := make([]int, 0, end-start+1)
for j := start; j <= end; j++ {
ans = append(ans, seqPos[j])
}
return ans
}
if sub, ok := b.QueryMask(label); ok {
sortSmall(sub)
ans := make([]int, 0)
for _, it := range sub {
in := selected[it]
for j := in.l; j <= in.r; j++ {
ans = append(ans, seqPos[j])
}
}
for j := start; j <= end; j++ {
ans = append(ans, seqPos[j])
}
return ans
}
if policy == 0 {
if chosenStart == 0 || start < chosenStart {
chosenStart = start
chosenLabel = label
}
} else {
if chosenStart == -1 || start > chosenStart {
chosenStart = start
chosenLabel = label
}
}
}
if (policy == 0 && chosenStart != 0) || (policy == 1 && chosenStart != -1) {
selected = append(selected, Interval{chosenStart, end})
b.Insert(chosenLabel, len(selected)-1)
lastEnd = end
}
}
return nil
}
func processSameLen(vals0, pos0 []int, d int) []int {
m := len(vals0)
if m == 0 {
return nil
}
px := make([]int, m+1)
st := make([]int, m+1)
seqPos := make([]int, m+1)
B := pow10d[d]
invB := powMod(B, p-2, p)
rem := 0
invPow := 1
for i := 1; i <= m; i++ {
v := vals0[i-1]
px[i] = px[i-1] ^ v
rem = int((int64(rem)*int64(B) + int64(v)) % int64(p))
invPow = int(int64(invPow) * int64(invB) % int64(p))
st[i] = int(int64(rem) * int64(invPow) % int64(p))
seqPos[i] = pos0[i-1]
}
if ans := repeatedPair(st, px, seqPos); ans != nil {
return ans
}
if ans := scheduleGreedy(st, px, seqPos, 0); ans != nil {
return ans
}
if ans := scheduleGreedy(st, px, seqPos, 1); ans != nil {
return ans
}
return nil
}
func check3(x, y, z int) []int {
i1, i2, i3 := pos[x], pos[y], pos[z]
v1, v2, v3 := x, y, z
if i1 > i2 {
i1, i2 = i2, i1
v1, v2 = v2, v1
}
if i2 > i3 {
i2, i3 = i3, i2
v2, v3 = v3, v2
}
if i1 > i2 {
i1, i2 = i2, i1
v1, v2 = v2, v1
}
rem := 0
rem = int((int64(rem)*int64(pow10d[dig[v1]]) + int64(v1)) % int64(p))
rem = int((int64(rem)*int64(pow10d[dig[v2]]) + int64(v2)) % int64(p))
rem = int((int64(rem)*int64(pow10d[dig[v3]]) + int64(v3)) % int64(p))
if rem == 0 {
return []int{i1, i2, i3}
}
return nil
}
func check4(a1, a2, a3, a4 int) []int {
idx := [4]int{pos[a1], pos[a2], pos[a3], pos[a4]}
val := [4]int{a1, a2, a3, a4}
for i := 1; i < 4; i++ {
j := i
for j > 0 && idx[j-1] > idx[j] {
idx[j-1], idx[j] = idx[j], idx[j-1]
val[j-1], val[j] = val[j], val[j-1]
j--
}
}
rem := 0
for i := 0; i < 4; i++ {
rem = int((int64(rem)*int64(pow10d[dig[val[i]]]) + int64(val[i])) % int64(p))
}
if rem == 0 {
return []int{idx[0], idx[1], idx[2], idx[3]}
}
return nil
}
func searchTriplets(cs []int) []int {
for _, c := range cs {
for x := 1; x <= n; x++ {
if x == c {
continue
}
y := x ^ c
if y < 1 || y > n || x >= y {
continue
}
if ans := check3(c, x, y); ans != nil {
return ans
}
}
}
return nil
}
func searchSquares(bits []int) []int {
m := len(bits)
for i := 0; i < m; i++ {
c := bits[i]
for j := i + 1; j < m; j++ {
d := bits[j]
cd := c ^ d
for x := 1; x <= n; x++ {
v2 := x ^ c
v3 := x ^ d
v4 := x ^ cd
if v2 < 1 || v2 > n || v3 < 1 || v3 > n || v4 < 1 || v4 > n {
continue
}
if !(x < v2 && x < v3 && x < v4) {
continue
}
if ans := check4(x, v2, v3, v4); ans != nil {
return ans
}
}
}
}
return nil
}
func randomSearch() []int {
seed := uint64(88172645463393265) ^ (uint64(n) << 32) ^ uint64(p)
rnd := func() uint64 {
seed ^= seed << 7
seed ^= seed >> 9
return seed
}
rn := func() int {
return int(rnd()%uint64(n)) + 1
}
for t := 0; t < 120000; t++ {
x := rn()
y := rn()
if x == y {
continue
}
z := x ^ y
if z < 1 || z > n || z == x || z == y {
continue
}
if ans := check3(x, y, z); ans != nil {
return ans
}
}
for t := 0; t < 120000; t++ {
x := rn()
y := rn()
z := rn()
if x == y || x == z || y == z {
continue
}
w := x ^ y ^ z
if w < 1 || w > n || w == x || w == y || w == z {
continue
}
if ans := check4(x, y, z, w); ans != nil {
return ans
}
}
return nil
}
func main() {
in := bufio.NewReaderSize(os.Stdin, 1<<20)
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
fmt.Fscan(in, &n, &p)
a = make([]int, n+1)
pos = make([]int, n+1)
dig = make([]int, n+1)
for i := 1; i <= n; i++ {
fmt.Fscan(in, &a[i])
pos[a[i]] = i
}
for v := 1; v <= n; v++ {
dig[v] = digitLen(v)
}
pow10d[0] = 1 % p
for d := 1; d <= 5; d++ {
pow10d[d] = int(int64(pow10d[d-1]) * 10 % int64(p))
}
if n <= 22 {
if ans := bruteForce(); ans != nil {
printAns(out, ans)
return
}
fmt.Fprintln(out, "No")
return
}
if p == 2 || p == 5 {
if ans := solveSpecial25(); ans != nil {
printAns(out, ans)
return
}
fmt.Fprintln(out, "No")
return
}
if ans := solveMultiples(); ans != nil {
printAns(out, ans)
return
}
px := make([]int, n+1)
st := make([]int, n+1)
seqPos := make([]int, n+1)
inv10 := powMod(10, p-2, p)
invPowLen := [6]int{}
invPowLen[0] = 1
for d := 1; d <= 5; d++ {
invPowLen[d] = int(int64(invPowLen[d-1]) * int64(inv10) % int64(p))
}
rem := 0
invPow := 1
for i := 1; i <= n; i++ {
v := a[i]
d := dig[v]
px[i] = px[i-1] ^ v
rem = int((int64(rem)*int64(pow10d[d]) + int64(v)) % int64(p))
invPow = int(int64(invPow) * int64(invPowLen[d]) % int64(p))
st[i] = int(int64(rem) * int64(invPow) % int64(p))
seqPos[i] = i
}
if ans := repeatedPair(st, px, seqPos); ans != nil {
printAns(out, ans)
return
}
if ans := scheduleGreedy(st, px, seqPos, 0); ans != nil {
printAns(out, ans)
return
}
if ans := scheduleGreedy(st, px, seqPos, 1); ans != nil {
printAns(out, ans)
return
}
byVals := make([][]int, 6)
byPos := make([][]int, 6)
for i := 1; i <= n; i++ {
d := dig[a[i]]
byVals[d] = append(byVals[d], a[i])
byPos[d] = append(byPos[d], i)
}
for d := 5; d >= 1; d-- {
if ans := processSameLen(byVals[d], byPos[d], d); ans != nil {
printAns(out, ans)
return
}
}
bits := make([]int, 0)
for b := 1; b <= n; b <<= 1 {
bits = append(bits, b)
}
seenC := make([]bool, n+1)
cs12 := make([]int, 0)
for _, b := range bits {
if b <= n && !seenC[b] {
seenC[b] = true
cs12 = append(cs12, b)
}
}
for i := 0; i < len(bits); i++ {
for j := i + 1; j < len(bits); j++ {
c := bits[i] ^ bits[j]
if c <= n && !seenC[c] {
seenC[c] = true
cs12 = append(cs12, c)
}
}
}
if ans := searchTriplets(cs12); ans != nil {
printAns(out, ans)
return
}
if n <= 10000 {
cs3 := make([]int, 0)
for i := 0; i < len(bits); i++ {
for j := i + 1; j < len(bits); j++ {
for k := j + 1; k < len(bits); k++ {
c := bits[i] ^ bits[j] ^ bits[k]
if c <= n && !seenC[c] {
seenC[c] = true
cs3 = append(cs3, c)
}
}
}
}
if ans := searchTriplets(cs3); ans != nil {
printAns(out, ans)
return
}
}
if ans := searchSquares(bits); ans != nil {
printAns(out, ans)
return
}
if ans := randomSearch(); ans != nil {
printAns(out, ans)
return
}
fmt.Fprintln(out, "No")
}