Submission #59654405

---

Source Code Expand

<?php
[$N] = ints();
for($i = 0; $i < $N; $i++)[$X1[], $Y1[]] = ints();
for($i = 0; $i < $N; $i++)[$X2[], $Y2[]] = ints();
$maxScore = 0;
$bestSize = 0;
for($split = 1; $split <= 20; $split++){
    $score = 0;
    unset($used, $added, $done);

    $size = floor(100000/$split);
    $map = array_fill(0, $split, array_fill(0, $split, 0));
    $added = array_fill(0, $split, array_fill(0, $split, " "));
    for($i = 0; $i < $N; $i++)$map[intdiv($X1[$i],$size)][intdiv($Y1[$i],$size)]++;
    for($i = 0; $i < $N; $i++)$map[intdiv($X2[$i],$size)][intdiv($Y2[$i],$size)]--;
    //o($map);
    foreach($map as $x => $row){
        foreach($row as $y => $v){
            $map2[$x][$y] = $v > 0 ? intdiv($v, 100)+1 : 0;
        }
    }
    $max = 0;
    $maxX = 0; $maxY = 0;
    for($i = 0; $i < $split; $i++){
        for($j = 0; $j < $split; $j++){
            if(chmax($max, $map[$i][$j])){
                $maxX = $i;
                $maxY = $j;
            }
        }
    }
    $xy = [[-1,0],[1,0],[0,-1],[0,1]];
    $length = 4*$size;
    $pq = new SplPriorityQueue();
    $used[$maxX][$maxY] = true;
    foreach($xy as list($dx, $dy)){
        if(isset($done[$maxX+$dx][$maxY+$dy]))continue;
        $done[$maxX+$dx][$maxY+$dy] = true;
        if(isset($map[$maxX+$dx][$maxY+$dy])){
            $pq->insert([$maxX+$dx, $maxY+$dy], $map[$maxX+$dx][$maxY+$dy]);
        }
    }
    while($pq->valid()){
        [$x, $y] = $pq->extract();
        $filledCellCountInAdjecentArea = 0;
        foreach($xy as list($dx, $dy)){
            if(isset($added[$x+$dx][$y+$dy]) && $added[$x+$dx][$y+$dy]===true)$filledCellCountInAdjecentArea++;
        }
        if($filledCellCountInAdjecentArea == 1){
            $length += 2*$size;
        }elseif($filledCellCountInAdjecentArea == 3){
            $length -= 2*$size;
        }
        if($length>400000)break;
        $added[$x][$y] = true;
        $score += $map[$x][$y];
        foreach($xy as list($dx, $dy)){
            if(isset($done[$x+$dx][$y+$dy]))continue;
            $done[$x+$dx][$y+$dy] = true;
            if(($map2[$x+$dx][$y+$dy]??0)>0){
                $pq->insert([$x+$dx, $y+$dy], $map[$x+$dx][$y+$dy]);
            }
        }
    }
    // $addedで" "が1に囲われている場所があればNG
    // $addedを上下左右1マス拡張する
    $added2 = array_fill(0, $split+2, array_fill(0, $split+2, ' '));
    for($i = 0; $i < $split; $i++){
        for($j = 0; $j < $split; $j++){
            $added2[$i+1][$j+1] = $added[$i][$j];
        }
    }
    //o($added2);
    // added2 を外から幅深さ優先探索で" "を1に変えていく
    $xy = [[-1,0],[1,0],[0,-1],[0,1]];
    $done = array_fill(0, $split+2, array_fill(0, $split+2, false));
    $done[0] = $done[$split+1] = array_fill(0, $split+2, true);
    foreach($done as $row)$row[0] = $row[$split+1] = true;
    $done[1][1] = true;
    $queue = new SplQueue();
    $queue->enqueue([1,1]);
    while(!$queue->isEmpty()){
        [$x, $y] = $queue->dequeue();
        foreach($xy as list($dx, $dy)){
            if(($added2[$x+$dx][$y+$dy]??1) === ' '){
                $added2[$x+$dx][$y+$dy] = 1;
                $queue->enqueue([$x+$dx, $y+$dy]);
            }
        }
    }
    //o($added2);
    // added2 の " " の数を数える
    $voidCount = 0;
    for($i = 0; $i < $split+2; $i++){
        for($j = 0; $j < $split+2; $j++){
            if($added2[$i][$j] === ' ')$voidCount++;
        }
    }
    if($voidCount > 0){
        break;
    }
    if(chmax($maxScore, $score)){
        $ans = $added;
        $bestSize = $size;
    }
}
error_log(strval($maxScore));
$N = 0;
$size = $bestSize;
//o($ans);
//exit;
foreach($ans as $x => $row){
    foreach($row as $y => $v){
        if($v === true){//今のセルが使っていて
            if(($ans[$x-1][$y]??" ") === " "){//左が使っていない
                $line[$x*$size][$y*$size] = [$x*$size, $y*$size+$size];$N++;
                $cx = $x*$size;
                $cy = $y*$size;
            }
            if(($ans[$x+1][$y]??" ") === " "){//右が使っていない
                $line[$x*$size+$size][$y*$size+$size] = [$x*$size+$size, $y*$size];$N++;
            }
            if(($ans[$x][$y-1]??" ") === " "){//上が使っていない
                $line[$x*$size+$size][$y*$size] = [$x*$size, $y*$size];$N++;
            }
            if(($ans[$x][$y+1]??" ") === " "){//下が使っていない
                $line[$x*$size][$y*$size+$size] = [$x*$size+$size, $y*$size+$size];$N++;
            }
        }
    }
}
echo $N, "\n";
//o($cy);
for($i = 0; $i < $N; $i++){
    echo $cx, " ", $cy, "\n";
    [$cx, $cy] = $line[$cx][$cy];
}

function str(){return trim(fgets(STDIN));}
function ints($n = false){
  if($n===false){
    $str = trim(fgets(STDIN));if($str == '')return [];
    return array_map('intval',explode(' ',$str));
  }else{$ret = [];for($i = 0; $i < $n; $i++)foreach(array_map('intval',explode(' ',trim(fgets(STDIN)))) as $j => $v)$ret[$j][] = $v;return $ret;}
}
function int(){return intval(trim(fgets(STDIN)));}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}
function isqrt($n):int{$res=intval(sqrt($n))+1;while($res*$res>$n)$res--;return $res;}
function popcount($x){$c=0;while($x){$x&=$x-1;++$c;}return$c;}
function swap(&$a,&$b){$tmp=$a;$a=$b;$b=$tmp;}
function o(...$val){
  if(count($val)==1)$val=array_shift($val);
  echo debug_backtrace()[0]['line'].")";
  if(is_array($val)){
    if(count($val) == 0)echo "empty array\n";
    elseif(!is_array(current($val)))echo "array: ",implode(" ", addIndex($val)),"\n";
    else{
      echo "array:array\n";
      if(isCleanArray($val))foreach($val as $row)echo implode(" ", addIndex($row)),"\n";
      else foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row)),"\n";
    }
  }else echo $val."\n";
}
function addIndex($val){if(!isCleanArray($val)){$val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);}return $val;}
function isCleanArray($array){$clean=true;$i = 0;foreach($array as $k=>$v){if($k != $i++)$clean = false;}return $clean;}
// 座圧対象の配列 -> [圧縮された配列,復元用のMap,圧縮用のMap]
function atsu($array){$a = array_flip($array);$fuku=array_flip($a);sort($fuku);$atsu = array_flip($fuku);foreach($array as $i=>$val)$array[$i]=$atsu[$val];return [$array, $fuku, $atsu];}
function atsu1($array){$a=array_flip($array);$fuku=array_flip($a);sort($fuku);array_unshift($fuku,0);unset($fuku[0]);$atsu=array_flip($fuku);foreach($array as $i=>$val)$array[$i]=$atsu[$val];return [$array, $fuku, $atsu];}
function median($a){sort($a);$n=count($a);return $n%2?$a[($n-1)/2]:($a[$n/2-1]+$a[$n/2])/2;}
function gcdAll($array){$gcd=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$gcd=gcd($gcd,$array[$i]);}return $gcd;}
function gcd($m, $n){if(!$n)return $m;return gcd($n, $m % $n);}
function lcmAll($array){$lcm=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$lcm=lcm($lcm,$array[$i]);}return $lcm;}
function lcm($a, $b) {return $a / gcd($a, $b) * $b;}

Submission Info

Judge Result