use std::time::Instant; macro_rules! get { ($t:ty) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.trim().parse::<$t>().unwrap() } }; ($($t:ty),*) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( $(iter.next().unwrap().parse::<$t>().unwrap(),)* ) } }; ($t:ty; $n:expr) => { (0..$n).map(|_| get!($t) ).collect::>() }; ($($t:ty),*; $n:expr) => { (0..$n).map(|_| get!($($t),*) ).collect::>() }; ($t:ty ;;) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse::<$t>().unwrap()) .collect::>() } }; ($t:ty ;; $n:expr) => { (0..$n).map(|_| get!($t ;;)).collect::>() }; } #[allow(unused_macros)] macro_rules! chmin { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_min = min!($($cmps),+); if $base > cmp_min { $base = cmp_min; true } else { false } }}; } #[allow(unused_macros)] macro_rules! chmax { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_max = max!($($cmps),+); if $base < cmp_max { $base = cmp_max; true } else { false } }}; } #[allow(unused_macros)] macro_rules! min { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::min($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::min($a, min!($($rest),+)) }}; } #[allow(unused_macros)] macro_rules! max { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::max($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::max($a, max!($($rest),+)) }}; } #[allow(unused_macros)] macro_rules! mat { ($e:expr; $d:expr) => { vec![$e; $d] }; ($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] }; } #[derive(Debug, Clone, Copy)] struct Requirement { digit: usize, value: usize, } #[derive(Debug, Clone)] struct Choice { requirements: [Requirement; 3], } #[derive(Debug, Clone)] struct Input { since: Instant, choices: Vec, } const CHOICES_COUNT: usize = 2048; const DIGIT_LEN: usize = 256; const TIME_LIMIT: f64 = 1.95; fn main() { let input = read_input(); let solution = solve(&input); write_output(&solution); } fn read_input() -> Input { let mut choices = vec![]; for _ in 0..CHOICES_COUNT { let (a, b, c, p, q, r) = get!(usize, usize, usize, usize, usize, usize); let requirements = [ Requirement { digit: a, value: p }, Requirement { digit: b, value: q }, Requirement { digit: c, value: r }, ]; let choice = Choice { requirements }; choices.push(choice); } let since = Instant::now(); let input = Input { since, choices }; input } fn solve(input: &Input) -> Vec { let mut counts = vec![0; DIGIT_LEN]; let mut solution = vec![0; DIGIT_LEN]; let mut best_solution = vec![0; DIGIT_LEN]; let mut best_score = 0; let mut total_count = 0; dfs( input, &mut solution, &mut best_solution, &mut best_score, &mut counts, &mut total_count, 0, ); eprintln!("score: {}", best_score); best_solution } fn dfs( input: &Input, solution: &mut Vec, best_solution: &mut Vec, best_score: &mut usize, counts: &mut [usize], total_count: &mut usize, depth: usize, ) -> bool { if *total_count % 1000 == 0 { let elapsed = (Instant::now() - input.since).as_secs_f64(); if elapsed > TIME_LIMIT { return false; } } if chmax!(*best_score, depth) { *best_solution = solution.clone(); } if depth == CHOICES_COUNT { return false; } for req in input.choices[depth].requirements.iter() { if counts[req.digit] == 0 || solution[req.digit] == req.value { counts[req.digit] += 1; *total_count += 1; solution[req.digit] = req.value; let over = dfs( input, solution, best_solution, best_score, counts, total_count, depth + 1, ); if over { return false; } counts[req.digit] -= 1; } } return true; } fn write_output(solution: &[usize]) { let mut result = String::new(); for v in solution.iter().rev() { if *v == 0 { result.push('0'); } else { result.push('1'); } } println!("{}", result); }