START_TIME = Time.utc.to_unix_ms TL = 1900 N = 2048 M = 256 INF = 1 << 29 RND = Random.new(2) macro debug(msg) {% if flag?(:trace) %} STDERR.puts({{msg}}) {% end %} end macro debugf(format_string, *args) {% if flag?(:trace) %} STDERR.printf({{format_string}}, {{*args}}) {% end %} end class IndexSet getter :upper def initialize(@upper : Int32) @que = [] of Int32 @pos = Array(Int32).new(@upper, -1) end def add(v) if @pos[v] == -1 @pos[v] = @que.size @que << v end end def remove(v) p = @pos[v] b = @que[-1] @que[p] = b @que.pop @pos[b] = p @pos[v] = -1 end def get_random @que[RND.rand(@que.size)] end def size @que.size end def to_s(io) @que.to_s(io) end end class Result property :bits, :score def initialize(@bits : Array(Int32), @score : Int32) end def to_s(io) io << @bits.map { |v| v == -1 ? 0 : v }.reverse.join end end struct Cond getter :var, :val def initialize(@var : Int32, @val : Int32) end end alias Term = Tuple(Cond, Cond, Cond) class Solver def initialize(@timelimit : Int64) @terms = Array(Term).new(N) do a, b, c, p, q, r = read_line.split.map(&.to_i) {Cond.new(a, p), Cond.new(b, q), Cond.new(c, r)} end @var_pos = Array(Array(Tuple(Int32, Int32))).new(M) { [] of Tuple(Int32, Int32) } N.times do |i| 3.times do |j| term = @terms[i][j] @var_pos[term.var] << {i, term.val} end end @best_result = Result.new(Array.new(M, -1), 0) @ans = Array(Int32).new(M, -1) @search_order = [0, 1, 2] @dfs_count = 0 @eval = Array(Int32).new(3, 0) @ok_count = Array(Int32).new(N, 0) @ng_count = Array(Int32).new(N, 0) @pass = Array(Bool).new(N) do |i| ts = @terms[i] [[0, 1], [1, 2], [2, 0]].any? { |ps| ts[ps[0]].var == ts[ps[1]].var && ts[ps[0]].var != ts[ps[1]].var } end end def solve solve_single() turn = 0 while true if Time.utc.to_unix_ms > @timelimit break end solve_single() turn += 1 end {% if flag?(:local) %} STDERR.puts("validate_score:#{score(@best_result.bits)}") {% end %} return @best_result end def solve_single @ans.fill(-1) @dfs_count = 0 @ok_count.fill(0) # @ng_count.fill(0) pos = 0 while pos < N if try_next(pos) while pos < N && @ok_count[pos] > 0 pos += 1 end if pos > @best_result.score @best_result.score = pos @best_result.bits[0, M] = @ans debug("best_score:#{pos}") end # if score(@ans) != pos # debug("validate_score:#{score(@ans)} score:#{pos}") # exit # end else break end if Time.utc.to_unix_ms > @timelimit break end end end def try_next(pos) shuffle(@search_order) 3.times do |i| t = @terms[pos][@search_order[i]] if @ans[t.var] == -1 @ans[t.var] = t.val @var_pos[t.var].each do |ps| p, v = ps if v == t.val @ok_count[p] += 1 # else # @ng_count[p] += 1 end end return true end end 300.times do set = IndexSet.new(N) set.add(pos) @dfs_count = 0 if try_dfs(pos, set) return true end if Time.utc.to_unix_ms > @timelimit break end end return false end def try_dfs(pos, set) # debug("try_dfs:#{pos} #{set}") if set.size == 0 return true end if @dfs_count > 100 || set.size > 7 return false end cur = set.get_random shuffle(@search_order) tc = 0 3.times do |i| t = @terms[cur][@search_order[i]] old = @ans[t.var] @ans[t.var] = t.val @var_pos[t.var].each do |ps| p, v = ps if v == t.val @ok_count[p] += 1 # @ng_count[p] -= 1 if p <= pos && @ok_count[p] == 1 set.remove(p) end elsif old != -1 @ok_count[p] -= 1 # @ng_count[p] += 1 if p <= pos && @ok_count[p] == 0 set.add(p) end end end tc += 1 if tc == 2 @dfs_count += 1 end if try_dfs(pos, set) return true end @ans[t.var] = old @var_pos[t.var].each do |ps| p, v = ps if v == t.val @ok_count[p] -= 1 # @ng_count[p] += 1 if p <= pos && @ok_count[p] == 0 set.add(p) end elsif old != -1 @ok_count[p] += 1 # @ng_count[p] -= 1 if p <= pos && @ok_count[p] == 1 set.remove(p) end end end end return false end def shuffle(a) (a.size - 1).times do |i| pos = RND.rand(a.size - i) + i a[i], a[pos] = a[pos], a[i] end end def score(ans) N.times do |i| if @terms[i].all? { |t| ans[t.var] != t.val } return i end end return N end end def main solver = Solver.new(START_TIME + TL) res = solver.solve puts res {% if flag?(:local) %} STDERR.puts("final_score:#{res.score}") {% end %} end main