#948720 (Go) No.274 The Wall

• 問題: No.274 The Wall
• ユーザー: 草苺奶昔
• 提出日時: 2024-02-08 23:50:09
• 言語: Go (1.22.1)
• 結果: WA
• 実行時間: -
• コード長: 9,728 bytes
• コンパイル時間: 14,809 ms
• コンパイル使用メモリ: 213,872 KB
• 実行使用メモリ: 206,348 KB
• 最終ジャッジ日時: 2024-02-08 23:50:37
• 合計ジャッジ時間: 24,796 ms
• ジャッジサーバーID （参考情報）: judge14 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-

ソースコード

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
}