結果

問題 No.1078 I love Matrix Construction
ユーザー aru aruaru aru
提出日時 2020-10-27 21:01:32
言語 Go
(1.22.1)
結果
AC  
実行時間 218 ms / 2,000 ms
コード長 5,824 bytes
コンパイル時間 15,186 ms
コンパイル使用メモリ 238,680 KB
実行使用メモリ 42,752 KB
最終ジャッジ日時 2024-07-21 22:03:15
合計ジャッジ時間 20,344 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 19 ms
6,784 KB
testcase_03 AC 64 ms
17,408 KB
testcase_04 AC 100 ms
19,456 KB
testcase_05 AC 87 ms
18,276 KB
testcase_06 AC 19 ms
7,424 KB
testcase_07 AC 5 ms
5,376 KB
testcase_08 AC 77 ms
19,328 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 218 ms
42,752 KB
testcase_11 AC 82 ms
21,888 KB
testcase_12 AC 140 ms
32,720 KB
testcase_13 AC 198 ms
36,992 KB
testcase_14 AC 119 ms
28,160 KB
testcase_15 AC 170 ms
32,128 KB
testcase_16 AC 5 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 11 ms
6,656 KB
testcase_19 AC 36 ms
10,496 KB
testcase_20 AC 34 ms
10,496 KB
testcase_21 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func out(x ...interface{}) {
	fmt.Fprintln(wr, x...)
}

func getI() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getF() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getI()
	}
	return ret
}

func getS() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)
	// this template is new version.
	// use getI(), getS(), getInts(), getF()
	N := getI()
	S := getInts(N)
	T := getInts(N)
	U := getInts(N)
	for i := 0; i < N; i++ {
		S[i]--
		T[i]--
	}

	ts := New(N * N)
	var id = func(i, j int) int {
		return i*N + j
	}
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			switch U[i] {
			case 0:
				ts.AddClause(id(S[i], j), true, id(j, T[i]), true)
			case 1:
				ts.AddClause(id(S[i], j), false, id(j, T[i]), true)
			case 2:
				ts.AddClause(id(S[i], j), true, id(j, T[i]), false)
			case 3:
				ts.AddClause(id(S[i], j), false, id(j, T[i]), false)
			}
		}
	}
	if !ts.Satisfiable() {
		out("-1")
		return
	}

	ans := ts.Answer()
	// test := make([][]int, N)
	for i := 0; i < N; i++ {
		// test[i] = make([]int, N)
		for j := 0; j < N; j++ {
			if ans[id(i, j)] {
				fmt.Fprint(wr, 1, " ")
				// test[i][j] = 1
			} else {
				fmt.Fprint(wr, 0, " ")
				// test[i][j] = 0
			}
		}
		fmt.Fprintln(wr)
	}

	// test = [][]int{{0, 0, 0}, {1, 0, 1}, {0, 0, 0}}
	// out(test)
	// for i := 0; i < N; i++ {
	// 	for j := 0; j < N; j++ {
	// 		x := test[S[i]][j] + 2*test[j][T[i]]
	// 		if x == U[i] {
	// 			out(i, j, x, U[i])
	// 		}
	// 	}
	// }
}

// TwoSat defines n, answer and scc
type TwoSat struct {
	n      int
	answer []bool
	scc    *SccGraph
}

// New creates a TwoSAT of n variables and 0 clauses
func New(n int) *TwoSat {
	ts := &TwoSat{
		n:      n,
		answer: make([]bool, n),
		scc:    NewGraph(n * 2),
	}
	return ts
}

func (ts *TwoSat) internalJudge(f bool, a int, b int) int {
	if f {
		return a
	}
	return b
}

// AddClause adds a clause.
func (ts *TwoSat) AddClause(i int, f bool, j int, g bool) {
	if !(0 <= i && i < ts.n) {
		panic("")
	}
	if !(0 <= j && j < ts.n) {
		panic("")
	}
	ts.scc.AddEdge(2*i+ts.internalJudge(f, 0, 1), 2*j+ts.internalJudge(g, 1, 0))
	ts.scc.AddEdge(2*j+ts.internalJudge(g, 0, 1), 2*i+ts.internalJudge(f, 1, 0))
}

// Satisfiable returns True if there is a truth assignment that satisfies all clauses
func (ts *TwoSat) Satisfiable() bool {
	id := ts.scc.SccIds().Second

	for i := 0; i < ts.n; i++ {
		if id[2*i] == id[2*i+1] {
			return false
		}
		ts.answer[i] = id[2*i] < id[2*i+1]
	}
	return true
}

// Answer returns a truth assignment that satisfies all clauses of the last call of satisfiable
func (ts *TwoSat) Answer() []bool {
	return ts.answer
}

type sccFromToPair struct {
	first, second int
}

type sccIdPair struct {
	First  int
	Second []int
}

type csr struct {
	start []int
	elist []int
}

func initCsr(n int, edges []*sccFromToPair) *csr {
	var ret csr
	ret.start = make([]int, n+1)
	ret.elist = make([]int, len(edges))
	for _, e := range edges {
		ret.start[e.first+1]++
	}
	for i := 1; i <= n; i++ {
		ret.start[i] += ret.start[i-1]
	}
	counter := make([]int, len(ret.start))
	copy(counter, ret.start)
	for _, e := range edges {
		ret.elist[counter[e.first]] = e.second
		counter[e.first]++
	}
	return &ret
}

// SccGraph :
type SccGraph struct {
	n     int
	edges []*sccFromToPair
}

// NewGraph :
func NewGraph(n int) *SccGraph {
	var s SccGraph
	s.n = n
	return &s
}

// AddEdge :
func (s *SccGraph) AddEdge(from, to int) {
	s.edges = append(s.edges, &sccFromToPair{from, to})
}

func (s *SccGraph) min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// SccIds :
func (s *SccGraph) SccIds() sccIdPair {
	g := initCsr(s.n, s.edges)
	nowOrd, groupNum := 0, 0
	visited := make([]int, 0, s.n)
	low := make([]int, s.n)
	ord := make([]int, s.n)
	ids := make([]int, s.n)
	for i := 0; i < s.n; i++ {
		ord[i] = -1
	}
	var dfs func(v int)
	dfs = func(v int) {
		low[v] = nowOrd
		ord[v] = nowOrd
		nowOrd++
		visited = append(visited, v)
		for i := g.start[v]; i < g.start[v+1]; i++ {
			to := g.elist[i]
			if ord[to] == -1 {
				dfs(to)
				low[v] = s.min(low[v], low[to])
			} else {
				low[v] = s.min(low[v], ord[to])
			}
		}
		if low[v] == ord[v] {
			for {
				u := visited[len(visited)-1]
				visited = visited[:len(visited)-1]
				ord[u] = s.n
				ids[u] = groupNum
				if u == v {
					break
				}
			}
			groupNum++
		}
	}
	for i := 0; i < s.n; i++ {
		if ord[i] == -1 {
			dfs(i)
		}
	}
	for i := 0; i < len(ids); i++ {
		ids[i] = groupNum - 1 - ids[i]
	}
	return sccIdPair{groupNum, ids}
}

// Scc :
func (s *SccGraph) Scc() [][]int {
	ids := s.SccIds()
	groupNum := ids.First
	counts := make([]int, groupNum)
	for _, x := range ids.Second {
		counts[x]++
	}
	groups := make([][]int, ids.First)
	for i := 0; i < groupNum; i++ {
		groups[i] = make([]int, 0, counts[i])
	}
	for i := 0; i < s.n; i++ {
		groups[ids.Second[i]] = append(groups[ids.Second[i]], i)
	}
	return groups
}
0