1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
package main
import (
"database/sql"
"flag"
"fmt"
"math/rand"
"os"
"os/exec"
_ "modernc.org/sqlite"
)
var file = flag.String("f", "cards", "cards file")
var sum = 0
var seg = []int{}
func build(a *sql.Rows, l, r, n int) {
if l == r {
a.Next()
a.Scan(&seg[n])
sum += seg[n]
return
}
m := (l + r) >> 1
build(a, l, m, n<<1)
build(a, m+1, r, n<<1|1)
seg[n] = seg[n<<1] + seg[n<<1|1]
}
func update(x, v, l, r, n int) {
if l == r {
seg[n] = v
return
}
m := (l + r) >> 1
if x <= m {
update(x, v, l, m, n<<1)
} else {
update(x, v, m+1, r, n<<1|1)
}
seg[n] = seg[n<<1] + seg[n<<1|1]
}
func query(v, l, r, n int) (int, int) {
if l == r {
return seg[n], l
}
m := (l + r) >> 1
if seg[n<<1] >= v {
return query(v, l, m, n<<1)
} else {
return query(v-seg[n<<1], m+1, r, n<<1|1)
}
}
func main() {
flag.Parse()
db, err := sql.Open("sqlite", *file)
if err != nil {
panic(err)
}
// Get number of cards
var N int
_ = db.QueryRow("SELECT COUNT(*) FROM cards").Scan(&N)
seg = make([]int, 4*N)
// Build segment tree
rows, err := db.Query("SELECT weight FROM cards")
if err != nil {
panic(err)
}
build(rows, 0, N-1, 1)
rows.Close()
// https://stackoverflow.com/questions/14094190/function-similar-to-getchar
// disable input buffering
exec.Command("stty", "-F", "/dev/tty", "cbreak", "min", "1").Run()
// do not display entered characters on the screen
exec.Command("stty", "-F", "/dev/tty", "-echo").Run()
// restore the echoing state when exiting
defer exec.Command("stty", "-F", "/dev/tty", "echo").Run()
for {
// Choose a random card
x := rand.Intn(sum)
fmt.Println(sum)
fmt.Println(x)
w, i := query(x, 0, N-1, 1)
fmt.Println(w)
fmt.Println(i)
// Get card contents from database
var key, val string
db.QueryRow("SELECT key, val FROM cards WHERE idx=?", i).Scan(&key, &val)
fmt.Println(key)
fmt.Println(val)
// Read user input
var b []byte = make([]byte, 1)
os.Stdin.Read(b)
if b[0] == byte('y') {
w >>= 1
sum -= w
} else if b[0] == byte('n') {
sum += w
w <<= 1
} else {
os.Exit(0)
}
// Update segment tree and database
update(i, w, 0, N-1, 1)
_, err = db.Exec("UPDATE cards SET weight=? WHERE idx=?", w, i)
if err != nil {
panic(err)
}
}
}
|
