httf2018qual.d

import std.stdio, std.string, std.conv, std.algorithm;
import std.exception, std.random, std.typecons, std.math;
import std.datetime;

auto sw=StopWatch(AutoStart.no);

class Problem{
  const int N=100;
  const int Q=1000;
  const int TL=6000; // ms

  int[N][N] a, b;
  alias Query=Tuple!(int, "x", int, "y", int, "h");
  Query[Q] ans;
  int bestScore=0, tmpScore=0, itr=0;
  auto rnd=Random(0);
  
  void stdInput(){
    foreach(i; 0..N)  
      a[i]=readln.split.to!(int[]);
  }

  void fileInput(){
    auto data=File("in.txt").byLine.map!split;
    for(int i=0; i<N; i++, data.popFront){
      a[i]=data.front.to!(int[]);
    }
    enforce(data.empty);
  }

  void solve(){
    init();
    while(sw.peek.msecs<(TL-50)){
      itr++;
      auto q=uniform(0, Q, rnd),
           x=uniform(0, N, rnd),
           y=uniform(0, N, rnd),
           h=uniform!"[]"(1, N, rnd);
      add(ans[q].y, ans[q].x, ans[q].h, -1);
      add(y, x, h);
      tmpScore=calc();
      if(tmpScore>bestScore){
        ans[q]=Query(x, y, h);
        bestScore=tmpScore;
      }else{
        add(y, x, h, -1);
        add(ans[q].y, ans[q].x, ans[q].h);        
      }
    }
  }

  void init(){
    foreach(i; 0..Q){
      ans[i].x=uniform(0, N, rnd);
      ans[i].y=uniform(0, N, rnd);
      ans[i].h=uniform!"[]"(1, N, rnd);
    }
    foreach(i; 0..N)foreach(j; 0..N) b[i][j]=0;    
    foreach(e; ans) add(e.y, e.x, e.h);
    bestScore=calc();
  }

  void add(int y, int x, int h, int sign=1){
    b[y][x]+=h*sign;
    foreach(z; 1..h){
      for(int dy=-z, dx=z-dy.abs; dy<=z; dy++, dx=z-dy.abs){
        if(ok(y+dy, x+dx)) b[y+dy][x+dx]+=(h-z)*sign;
        if(ok(y+dy, x-dx) && dx!=0) b[y+dy][x-dx]+=(h-z)*sign;
      }
    }
  }

  bool ok(int y, int x){
    return (0<=y && y<N && 0<=x && x<N);
  }

  int calc(){
    auto score=2e8.to!(int);
    foreach(i; 0..N)foreach(j; 0..N)
      score-=(a[i][j]-b[i][j]).abs;
    return score;
  }

  void stdOutput(){
    writeln(Q);
    foreach(l; ans){
      writeln(l.x, " ", l.y, " ", l.h);
    }
  }

  void fileOutput(){
    auto f=File("out.txt", "w");
    f.writeln(Q); 
    foreach(l; ans){
      f.writeln(l.x, " ", l.y, " ", l.h);
    }
  }

  void show(){
    stderr.writeln("itr = ", itr);
    stderr.writeln("score = ", bestScore);
  }
}

void main(){
  sw.start;

  auto p=new Problem;
  if(true){
    p.stdInput;
    p.solve;
    p.stdOutput;
  }else{
    p.fileInput;
    p.solve;
    p.fileOutput;
  }

  sw.stop;
  p.show;
}