結果

問題 No.274 The Wall
ユーザー 草苺奶昔
提出日時 2024-02-08 23:50:09
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 9,728 bytes
コンパイル時間 14,401 ms
コンパイル使用メモリ 234,396 KB
実行使用メモリ 205,016 KB
最終ジャッジ日時 2024-09-28 12:55:41
合計ジャッジ時間 24,541 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
    "bufio"
    "fmt"
    "os"
)
func main() {
    放置国旗()
    // yosupo()
    yuki274()
}
// https://atcoder.jp/contests/practice2/tasks/practice2_h
// 1-N号旗设置位置(放置国旗)
// 第i号旗可以设置在xi位置或者yi位置
// !任意两面旗距离需要大于D
// 是否可以设置旗子
// 1≤N≤1000
// D,Xi,Yi<=1e9
//
// 命题i:第i个棋子放在xi位置,检查是否满足条件
func 放置国旗() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var n, d int
    fmt.Fscan(in, &n, &d)
    x, y := make([]int, n), make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &x[i], &y[i])
    }
    ts := NewTwoSat(n)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            // 00
            if abs(x[i]-x[j]) < d {
                ts.AddNand(i, j)
            }
            // 01
            if abs(x[i]-y[j]) < d {
                ts.AddNand(i, ts.Rev(j))
            }
            // 10
            if abs(y[i]-x[j]) < d {
                ts.AddNand(ts.Rev(i), j)
            }
            // 11
            if abs(y[i]-y[j]) < d {
                ts.AddNand(ts.Rev(i), ts.Rev(j))
            }
        }
    }
    res, ok := ts.Solve()
    if !ok {
        fmt.Fprintln(out, "No")
        return
    }
    fmt.Fprintln(out, "Yes")
    for i := 0; i < n; i++ {
        if res[i] {
            fmt.Fprintln(out, x[i])
        } else {
            fmt.Fprintln(out, y[i])
        }
    }
}
// No.274 The Wall-墙壁
// https://yukicoder.me/problems/no/274
// 用n个砖块构建墙壁,每个砖长度为m
// 每个砖块上有一段颜色,砖块可以180度旋转
// 将这n个砖块拼接成一面墙壁,使得每一列存在颜色的部分最多只有一个
// 问是否能够拼接成功
// n<=2000,m<=4000
// n个命题分别为[第i个砖块不旋转]
// 每两个之间验证四种情况
func yuki274() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var n, m int
    fmt.Fscan(in, &n, &m)
    color := make([][]int, n) // [left,right]
    for i := 0; i < n; i++ {
        var l, r int
        fmt.Fscan(in, &l, &r)
        color[i] = []int{l, r}
    }
    isOverlapped := func(left1, right1, left2, right2 int) bool {
        start := max(left1, left2)
        end := min(right1, right2)
        return start <= end
    }
    // n个命题分别为[第i个砖块不旋转]
    // 每两个之间验证四种情况
    ts := NewTwoSat(n)
    for i := 0; i < n; i++ {
        left1, right1 := color[i][0], color[i][1]
        revLeft1, revRight1 := m-1-right1, m-1-left1
        for j := i + 1; j < n; j++ {
            left2, right2 := color[j][0], color[j][1]
            revLeft2, revRight2 := m-1-right2, m-1-left2
            // 1. 两个砖块都不旋转
            if isOverlapped(left1, right1, left2, right2) {
                ts.AddNand(i, j)
            }
            // 2. 第一个砖块旋转,第二个砖块不旋转
            if isOverlapped(revLeft1, revRight1, left2, right2) {
                ts.AddNand(ts.Rev(i), j)
            }
            // 3. 第一个砖块不旋转,第二个砖块旋转
            if isOverlapped(left1, right1, revLeft2, revRight2) {
                ts.AddNand(i, ts.Rev(j))
            }
            // 4. 两个砖块都旋转
            if isOverlapped(revLeft1, revRight1, revLeft2, revRight2) {
                ts.AddNand(ts.Rev(i), ts.Rev(j))
            }
        }
    }
    _, ok := ts.Solve()
    if !ok {
        fmt.Fprintln(out, "NO")
        return
    }
    fmt.Fprintln(out, "YES")
}
// No.470 Inverse S+T Problem
// https://yukicoder.me/problems/no/470/editorial
// 给定n个长度为3的字符串,由小写字母和大写字母组成
// 求2n个非空串Si和Ti，使得 S[i] + T[i] = U[i],且这2n个串都不相同
// n<=1e5
// 长度为3的字符串划分成两个非空部分,要么是1/2,要么是2/1 => 2SAT
// n很大的时候一定有重复串,可以排除
// !n不大的时候用2SAT解决 :命题i代表S[i]用1个字符
func yuki470() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var n int
    fmt.Fscan(in, &n)
    words := make([]string, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &words[i])
    }
    // 只使用a-z和A-Z的字符,一个字符一定有重复的
    if n > 26*2 {
        fmt.Fprintln(out, "Impossible")
        return
    }
    ts := NewTwoSat(n)
    // 枚举所有的对,看哪些s[i]不能同时用一个字符划分
    // かぶさる可能性のあるものを反転させたものをグラフに追加する  ??
    for i := 0; i < n; i++ {
        w1 := words[i]
        for j := i + 1; j < n; j++ {
            w2 := words[j]
            // 1 1
            s1, t1, s2, t2 := w1[0:1], w1[1:], w2[0:1], w2[1:]
            if s1 == s2 || t1 == t2 {
                ts.AddNand(i, j)
            }
            // 1 2
            s1, t1, s2, t2 = w1[0:1], w1[1:], w2[0:2], w2[2:]
            if s1 == t2 || t1 == s2 {
                ts.AddNand(i, ts.Rev(j))
            }
            // 2 1
            s1, t1, s2, t2 = w1[0:2], w1[2:], w2[0:1], w2[1:]
            if s1 == t2 || t1 == s2 {
                ts.AddNand(ts.Rev(i), j)
            }
            // 2 2
            s1, t1, s2, t2 = w1[0:2], w1[2:], w2[0:2], w2[2:]
            if s1 == s2 || t1 == t2 {
                ts.AddNand(ts.Rev(i), ts.Rev(j))
            }
        }
    }
    res, ok := ts.Solve()
    if !ok {
        fmt.Fprintln(out, "Impossible")
        return
    }
    for i := 0; i < n; i++ {
        if res[i] {
            s, t := words[i][0:1], words[i][1:]
            fmt.Fprint(out, s, " ", t)
        } else {
            s, t := words[i][0:2], words[i][2:]
            fmt.Fprint(out, s, " ", t)
        }
        fmt.Fprintln(out)
    }
}
// No.1078 I love Matrix Construction
// https://yukicoder.me/problems/no/1078
// 给定长为n的数组S,T,U
// 问能否构建出满足以下条件的n*n矩阵A
// 1. A[i][j] 为0/1
// 2. 对所有的 (i,j), A[S[i]][j]+A[j][T[i]]*2 != U[i]
// n<=500
func yuki1078() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var n int
    fmt.Fscan(in, &n)
    S := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &S[i])
        S[i]--
    }
    T := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &T[i])
        T[i]--
    }
    U := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &U[i])
    }
    // 条件i为A[i][j]取0
    ts := NewTwoSat(n * n)
    for i := 0; i < n; i++ {
        si := S[i]
        ti := T[i]
        for j := 0; j < n; j++ {
            pos1 := si*n + j
            pos2 := j*n + ti
            if U[i] == 0 {
                ts.AddNand(pos1, pos2) // 0,0
            } else if U[i] == 1 {
                ts.AddNand(ts.Rev(pos1), pos2) //1,0
            } else if U[i] == 2 {
                ts.AddNand(pos1, ts.Rev(pos2)) //0,1
            } else if U[i] == 3 {
                ts.AddNand(ts.Rev(pos1), ts.Rev(pos2)) //1,1
            }
        }
    }
    res, ok := ts.Solve()
    if !ok {
        fmt.Fprintln(out, -1)
        return
    }
    matrix := make([][]int, n)
    for i := 0; i < n; i++ {
        matrix[i] = make([]int, n)
    }
    for i, v := range res {
        if !v {
            matrix[i/n][i%n] = 1
        }
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            fmt.Fprint(out, matrix[i][j], " ")
        }
        fmt.Fprintln(out)
    }
}
// https://judge.yosupo.jp/problem/two_sat
// N 変数  M 節の 2 Sat が与えられる。充足可能か判定し、可能ならば割り当てを一つ求めてください。
func yosupo() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var p, cnf string
    var n, m int
    fmt.Fscan(in, &p, &cnf, &n, &m)
    ts := NewTwoSat(n)
    for i := 0; i < m; i++ {
        var a, b, c int
        fmt.Fscan(in, &a, &b, &c)
        if a < 0 {
            a = ts.Rev(-a - 1)
        } else {
            a--
        }
        if b < 0 {
            b = ts.Rev(-b - 1)
        } else {
            b--
        }
        ts.AddOr(a, b)
    }
    res, ok := ts.Solve()
    if !ok {
        fmt.Fprintln(out, "s UNSATISFIABLE")
        return
    }
    fmt.Fprintln(out, "s SATISFIABLE")
    fmt.Fprint(out, "v ")
    for i, v := range res {
        if v {
            fmt.Fprint(out, i+1, " ")
        } else {
            fmt.Fprint(out, -(i + 1), " ")
        }
    }
    fmt.Fprintln(out, 0)
}
type TwoSat struct {
    size int
    scc  *scc
}
func NewTwoSat(n int) *TwoSat {
    return &TwoSat{size: n, scc: newScc(n + n)}
}
// u -> v <=> !v -> !u
func (ts *TwoSat) AddIf(u, v int) {
    ts.scc.AddEdge(u, v)
    ts.scc.AddEdge(ts.Rev(v), ts.Rev(u))
}
// u or v <=> !u -> v
func (ts *TwoSat) AddOr(u, v int) {
    ts.AddIf(ts.Rev(u), v)
}
// u nand v <=> u -> !v
func (ts *TwoSat) AddNand(u, v int) {
    ts.AddIf(u, ts.Rev(v))
}
// u <=> !u -> u
func (ts *TwoSat) SetTrue(u int) {
    ts.scc.AddEdge(ts.Rev(u), u)
}
// !u <=> u -> !u
func (ts *TwoSat) SetFalse(u int) {
    ts.scc.AddEdge(u, ts.Rev(u))
}
func (ts *TwoSat) Rev(u int) int {
    if u >= ts.size {
        return u - ts.size
    }
    return u + ts.size
}
func (ts *TwoSat) Solve() (res []bool, ok bool) {
    ts.scc.Build()
    res = make([]bool, ts.size)
    for i := 0; i < ts.size; i++ {
        if ts.scc.belong[i] == ts.scc.belong[ts.Rev(i)] {
            return
        }
        res[i] = ts.scc.belong[i] > ts.scc.belong[ts.Rev(i)]
    }
    ok = true
    return
}
// kosaraju算法求强连通分量.
type scc struct {
    graph  [][]int32
    belong []int32 //每个顶点所属的强连通分量的编号
    rGraph [][]int32
    order  []int32
    used   []bool
}
func newScc(n int) *scc {
    return &scc{graph: make([][]int32, n)}
}
func (scc *scc) AddEdge(from, to int) {
    scc.graph[from] = append(scc.graph[from], int32(to))
}
func (scc *scc) Build() {
    n32 := int32(len(scc.graph))
    scc.rGraph = make([][]int32, n32)
    for i := int32(0); i < n32; i++ {
        for _, e := range scc.graph[i] {
            scc.rGraph[e] = append(scc.rGraph[e], i)
        }
    }
    scc.belong = make([]int32, n32)
    for i := range scc.belong {
        scc.belong[i] = -1
    }
    scc.used = make([]bool, n32)
    for i := int32(0); i < n32; i++ {
        scc.dfs(i)
    }
    for i, j := 0, len(scc.order)-1; i < j; i, j = i+1, j-1 {
        scc.order[i], scc.order[j] = scc.order[j], scc.order[i]
    }
    ptr := int32(0)
    for _, v := range scc.order {
        if scc.belong[v] == -1 {
            scc.rdfs(v, ptr)
            ptr++
        }
    }
}
func (scc *scc) dfs(idx int32) {
    tmp := scc.used[idx]
    scc.used[idx] = true
    if tmp {
        return
    }
    for _, e := range scc.graph[idx] {
        scc.dfs(e)
    }
    scc.order = append(scc.order, idx)
}
func (scc *scc) rdfs(idx int32, cnt int32) {
    if scc.belong[idx] != -1 {
        return
    }
    scc.belong[idx] = cnt
    for _, e := range scc.rGraph[idx] {
        scc.rdfs(e, cnt)
    }
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0