Submission #1869850

---

Source Code Expand

// Try Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017
// author: Leonardone @ NEETSDKASU

struct XorShift { value: u64 }

impl XorShift {
    fn new() -> XorShift { XorShift{ value: 88172645463325252 } }
    fn gen(&mut self) -> u64 {
        self.value = self.value ^ (self.value << 13);
        self.value = self.value ^ (self.value >> 17);
        self.value = self.value ^ (self.value << 5);
        self.value
    }
    fn next(&mut self, d: u64) -> u64 { self.gen() % d }
} 

fn main() {

    use std::time::{Duration, SystemTime};
    let now = SystemTime::now();
    let loop_out_time = now + Duration::from_millis(20000);
    let final_time = now + Duration::from_millis(29000);
    
    let mut stdin = String::new();
    {
        use std::io::Read;
        std::io::stdin().read_to_string(&mut stdin).expect("failed to read string");    
    }
    let mut stdin = stdin.split_whitespace();
    
    macro_rules! get {
        () => ( stdin.next().unwrap().parse().unwrap() );
        ($t:ty) => ( stdin.next().unwrap().parse::<$t>().unwrap() );
    }

    let v = get!(usize);
    let e = get!(u32);
    
    let mut table = vec![vec![0; v+1]; v+1];
    for _ in 0..e {
        let a = get!(usize);
        let b = get!(usize);
        table[a][b] = 100;
        table[b][a] = 100;
    }
    let table = table;
    
    let vemb = get!(usize);
    let s = (vemb as f64).sqrt() as usize;
    let mut rand = XorShift::new();
    
    macro_rules! calc { ($gan:ident; $conn:ident; $g:expr) => {{
        let a = $gan[$g];
        let mut tmp = 0;
        for &h in &$conn[$g] {
            let b = $gan[h];
            tmp += table[a][b];
        }
        tmp
    }}}
    
    macro_rules! total { ($gan:ident; $conn:ident; $gc:expr) => {{
        let mut tmp = 0;
        for g in 1..$gc+1 {
            tmp += calc!($gan; $conn; g);
        }
        tmp / 2        
    }}}
    
    macro_rules! clime { ($gc:expr; $gan:ident; $conn:ident) => {
        {
            let mut cc = 0;
            for g1 in 1..$gc {
                let zr = $gan[g1] == 0;
                for g2 in g1+1..$gc+1 {
                    if zr && $gan[g2] == 0 { continue; }
                    let old_score = calc!($gan; $conn; g1) + calc!($gan; $conn; g2);
                    $gan.swap(g1, g2);
                    let new_score = calc!($gan; $conn; g1) + calc!($gan; $conn; g2);
                    if old_score > new_score {
                        $gan.swap(g1, g2);
                        continue;
                    }
                    cc += 1;
                }
            }
            if cc == 0 { break; }
        }
    }}
    
    let (gc, group, conn) = make_group(v, vemb, s);
    
    let mut gsize = gc;
    let mut groupx = group.clone();
    let mut connx = conn.clone();
    let mut gvs = vec![0; gsize+1];
    for i in 1..v+1 {
        gvs[i] = i;
    }
    
    for _ in 0..100 { clime!(gsize; gvs; connx); }
    let mut max_score = total!(gvs; connx; gsize);
    
    loop {
        
        let now = SystemTime::now();
        if now.cmp(&loop_out_time) == std::cmp::Ordering::Greater {
            break;
        }
    
        let (gsz, grp, cnn) = match make_joint(v, s, gc, &group, &conn, &mut rand) {
            Some(x) => x,
            None => continue,
        };
                
        let mut gan = vec![0; gsz+1];
        for i in 1..v+1 {
            gan[i] = i;
        }        
        for _ in 0..40 { clime!(gsz; gan; cnn); }
        
        let score = total!(gan; cnn; gsz);
        
        if score > max_score {
            max_score = score;
            gvs = gan;
            gsize = gsz;
            groupx = grp;
            connx = cnn;
        }
    }
    
    loop {
        let now = SystemTime::now();
        if now.cmp(&final_time) == std::cmp::Ordering::Greater {
            break;
        }
        clime!(gsize; gvs; connx);
    }

    let mut res = vec![0; v];
    for g in 1..gvs.len() {
        let vt = gvs[g];
        if vt == 0 { continue; }
        res[vt-1] = g;
    }
        
    for g in res {
        print!("{}", groupx[g].len());
        for vt in &groupx[g] {
            print!(" {}", vt);
        }
        println!();
    }
    
}    
    
fn make_group(v: usize, vemb: usize, s: usize) -> (usize, Vec<Vec<usize>>, Vec<Vec<usize>>) {
    use std::cmp::Ordering;
    
    #[derive(Copy, Clone, Eq, PartialEq)]
    struct Vertex {
        pos: usize,
        x: i32,
        y: i32,
        dist: i32,
    }
    
    impl Ord for Vertex {
        fn cmp(&self, other: &Vertex) -> Ordering { self.dist.cmp(&other.dist) }
    }
    
    impl PartialOrd for Vertex {
        fn partial_cmp(&self, other: &Vertex) -> Option<Ordering> { Some(self.cmp(other)) }
    }
    
    let mut vs = vec![];
    for i in 0..vemb {
        let x = (i % s) as i32;
        let y = (i / s) as i32;
        let dx = x - s as i32 / 2;
        let dy = y - s as i32 / 2;
        vs.push(Vertex{ pos: i, x: x, y: y, dist: dx * dx + dy * dy });
    }
    
    vs.sort();
    
    let mut group = vec![0; vemb];
    let mut gc = 0;
    let mut rem = vemb;
    for vt in vs {
        if group[vt.pos] != 0 { continue; }
        if rem + gc <= v { break; }
        gc += 1;
        group[vt.pos] = gc;
        rem -= 1;
        let x = vt.x + if vt.x % 2 == 0 { 1 } else { -1 };
        let y = vt.y + if vt.y % 2 == 0 { 1 } else { -1 };
        if x < 0 || x >= s as i32 || y < 0 || y >= s as i32 {
            continue;
        }
        if rem + gc <= v { break; }
        let p = y * s as i32 + x;
        group[p as usize] = gc;
        rem -= 1;
    }
    for i in 0..group.len() {
        if group[i] == 0 {
            gc += 1;
            group[i] = gc;
        }
    }
    
    use std::collections::HashSet;
    
    let mut conn: Vec<HashSet<usize>> = vec![HashSet::new(); gc+1];
    
    for i in 0..group.len() {
        let g = group[i];
        if (i+1) < vemb && (i+1) % s != 0 {
            conn[g].insert(group[i+1]); // right
            if (i+s+1) < vemb {
                conn[g].insert(group[i+s+1]); // right-down
            }
            if i >= s-1 {
                conn[g].insert(group[i-(s-1)]); // right-up
            }
        }
        if i % s != 0 {
            conn[g].insert(group[i-1]); // left
            if (i+s-1) < vemb {
                conn[g].insert(group[i+s-1]); // left-down
            }
            if i >= s+1 {
                conn[g].insert(group[i-(s+1)]); // left-up
            }
        }
        if i+s < vemb {
            conn[g].insert(group[i+s]); // down
        }
        if i >= s {
            conn[g].insert(group[i-s]); // up
        }
        conn[g].remove(&g);
    }
    let conn = conn.iter().map(|xs| {
        let mut vs = vec![];
        for &x in xs {
            vs.push(x);
        }
        vs
    }).collect();
    
    let group = {
        let mut tmp = vec![vec![]; gc+1];
        for i in 0..group.len() {
            let g = group[i];
            tmp[g].push(i+1);
        }
        tmp
    };
    
    (gc, group, conn)
}

fn make_joint(v: usize, s: usize, gcx: usize, groupx: &Vec<Vec<usize>>, connx: &Vec<Vec<usize>>, rand: &mut XorShift) -> Option<(usize, Vec<Vec<usize>>, Vec<Vec<usize>>)> {
    
    let mut gc = gcx;
    let mut group = vec![vec![]; gc+1];
    let mut conn = vec![vec![]; gc+1];
    for i in 1..gc+1 {
        group[i] = groupx[i].clone();
        conn[i] = connx[i].clone();
    }
    
    let sz = std::cmp::max(20, gc / 3);
    
    for _ in 0..sz {
        if gc <= v + 5 { break; }
    
        let base = rand.next(gc as u64) as usize + 1;
        if base >= conn.len() { return Option::None; }
        let tagi = rand.next(conn[base].len() as u64) as usize;
        let tagg = conn[base][tagi];
        conn[base].swap_remove(tagi);
        if tagg >= conn.len() { return Option::None; }
        for i in 0..conn[tagg].len() {
            let h = conn[tagg][i];
            if h == base { continue; }
            if h >= conn.len() { return Option::None; }
            for j in 0..conn[h].len() {
                if conn[h][j] == tagg {
                    conn[h][j] = base;
                    break;
                }
            }
            conn[base].push(h);
        }
        conn[base].sort();
        conn[base].dedup();
        conn.swap_remove(tagg);
        if tagg != gc {
            for i in 0..conn[tagg].len() {
                let h = conn[tagg][i];
                if h >= conn.len() { return Option::None; }
                for j in 0..conn[h].len() {
                    if conn[h][j] == gc {
                        conn[h][j] = tagg;
                        break;
                    }
                }
            }
        }
        for i in 0..group[tagg].len() {
            let h = group[tagg][i];
            group[base].push(h);
        }
        group.swap_remove(tagg);
        
        gc -= 1;
        
        if gc+1 != group.len() { return Option::None; }
        if gc+1 != conn.len() { return Option::None; }
        
    }

    for h in 0..conn.len() {
        for j in 0..conn[h].len() {
            if conn[h][j] >= conn.len() {
                return Option::None;
            }
        }
    }
    
    for i in 1..group.len() {
        if group[i].len() < 2 { continue; }
        for j in 0..group[i].len() {
            let a = group[i][j]-1;
            let mut f = true;
            for k in 0..group[i].len() {
                if j == k { continue; }
                let b = group[i][k]-1;
                let (a, b) = if a > b { (b, a) } else { (a, b) };
                let d = b - a;
                if d == s { f = false; break; }
                if (d == 1 || d == s+1) && b % s != 0 { f = false; break; }
                if d == s-1 && a % s != 0  { f = false; break; }
            }
            if f { return Option::None; }
        }
    }
    
    Option::Some((gc, group, conn))
}

Submission Info

Judge Result