poyo-poyo
2/19/2018 - 2:53 AM

## 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)
}

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);
tmpScore=calc();
if(tmpScore>bestScore){
ans[q]=Query(x, y, h);
bestScore=tmpScore;
}else{
}
}
}

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;
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;
}
``````