TopCoder Open Marathon 2014 Round 3 CollageMaker

CollageMaker.cpp

/*
TopCoder Open Marathon 2014 Round 3 CollageMaker
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdarg>
#include <cmath>
#include <ctime>

using namespace std;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

void log(const char *f, ...)
{
	va_list a;
	va_start(a, f);
	vfprintf(stderr, f, a);
	fflush(stderr);
	va_end(a);
}

struct PIC
{
	int w, h;
	unsigned char data[100][128];
};

struct TREE
{
	int x, y, w, h;
	int pic;
	int score;
	bool squre;
	vector<TREE> child;
};

int W, H;
unsigned char target[300][512];
PIC source[200];

//  0 0 0 1
//  0 0 0 1
//  2 2 2 3
//	4: hor
//	5: ver
PIC scaled[6][200];
bool used[200];

void scale(PIC *dst, PIC *src, int w, int h)
{
	//	TODO: speed up
	if (w>src->w || h>src->h)
	{
		dst->w = dst->h = -1;
		return;
	}

	if (src->w==0 || src->h==0)
	{
		dst->w = dst->h = 0;
		return;
	}

	auto func = [](int srcw, int dstw,
		vector<int> &srcx, vector<int> &dstx, vector<int> &intrx) -> void
	{
		for (int sx=0; sx<srcw; sx++)
		{
			int sl = sx * dstw;
			int sr = sl + dstw;
			for (int dx=0; dx<dstw; dx++)
			{
				int dl = dx * srcw;
				int dr = dl + srcw;
				int f = max(sl, dl);
				int t = min(sr, dr);
				if (f < t)
				{
					srcx.push_back(sx);
					dstx.push_back(dx);
					intrx.push_back(t-f);
				}
			}
		}
	};

	vector<int> srcx, dstx, intrx;
	vector<int> srcy, dsty, intry;
	func(src->w, w, srcx, dstx, intrx);
	func(src->h, h, srcy, dsty, intry);

	int data[128][128];
	for (int y=0; y<h; y++)
	for (int x=0; x<w; x++)
		data[y][x] = 0;
	for (int y=0; y<(int)srcy.size(); y++)
	for (int x=0; x<(int)srcx.size(); x++)
		data[dsty[y]][dstx[x]] += intrx[x]*intry[y] * src->data[srcy[y]][srcx[x]];

	dst->w = w;
	dst->h = h;
	int a = src->w * src->h;
	for (int y=0; y<h; y++)
	for (int x=0; x<w; x++)
		dst->data[y][x] = (2*data[y][x] + a) / (2*a);
}

void split(TREE &t, int cs, int d)
{
	if (!t.squre)
		return;

	if (d>0)
	{
		for (TREE &c : t.child)
			split(c, cs, d-1);
	}
	else
	{
		int bestscore = t.score;

		for (int sp=0; sp<3; sp++)
		{
			vector<TREE> C;

			switch (sp)
			{
			case 0:
				for (int y=t.y; y<H && y<t.y+t.h; y+=cs)
				for (int x=t.x; x<W && x<t.x+t.w; x+=cs)
				{
					TREE c;
					c.x = x;
					c.y = y;
					c.w = min(W-x, cs);
					c.h = min(H-y, cs);
					c.pic = -1;
					c.squre = true;
					C.push_back(c);
				}
				break;
			case 1:
				for (int y=t.y; y<H && y<t.y+t.h; y+=cs)
				for (int x=t.x; x<W && x<t.x+t.w; x+=cs*2)
				{
					TREE c;
					c.x = x;
					c.y = y;
					c.w = min(W-x, cs*2);
					c.h = min(H-y, cs);
					c.pic = -1;
					C.push_back(c);
				}
				break;
			case 2:
				for (int y=t.y; y<H && y<t.y+t.h; y+=cs*2)
				for (int x=t.x; x<W && x<t.x+t.w; x+=cs)
				{
					TREE c;
					c.x = x;
					c.y = y;
					c.w = min(W-x, cs);
					c.h = min(H-y, cs*2);
					c.pic = -1;
					C.push_back(c);
				}
				break;
			}

			if (t.child.size()>0)
			{
				for (TREE &c : t.child)
					used[c.pic] = false;
			}
			else
				used[t.pic] = false;

			int cscore = 0;

			for (TREE &c : C)
			{
				int ci;
				if (c.w==cs*2 && c.h==cs) ci = 4;
				else if (c.w==cs && c.h==cs*2) ci = 5;
				else ci = int(c.h!=cs)*2 + int(c.w!=cs);
				int score = 0xfffffff;
				int best = -1;

				for (int i=0; i<200; i++)
				if (!used[i] && scaled[ci][i].w==c.w && scaled[ci][i].h==c.h)
				{
					//if (scaled[ci][i].w!=c.w ||
					//	scaled[ci][i].h!=c.h)
					//	log("! %d %d %d %d\n", scaled[ci][i].w, c.w, scaled[ci][i].h, c.h);
					int s = 0;
					for (int y=0; y<c.h; y++)
					for (int x=0; x<c.w; x++)
					{
						int t = (int)scaled[ci][i].data[y][x] - target[c.y+y][c.x+x];
						s += t*t;
					}
					if (s<score)
					{
						score = s;
						best = i;
					}
				}

				c.score = score;
				c.pic = best;
				if (best>=0)
					used[best] = true;
				cscore += score;
			}

			if (cscore < bestscore)
			{
				bestscore = cscore;
				t.child = C;
			}
			else
			{
				for (TREE &c : C)
					if (c.pic>=0)
						used[c.pic] = false;

				if (t.child.size()>0)
				{
					for (TREE &c : t.child)
						used[c.pic] = true;
				}
				else
					used[t.pic] = true;
			}
		}
	}
}

int calcscore(TREE &t)
{
	int s = 0;
	if (t.child.size()>0)
		for (TREE &c : t.child)
			s += calcscore(c);
	else
		s += t.score;
	return s;
}

void output(TREE &t, vector<int> &ret)
{
	if (t.child.size()>0)
	{
		for (TREE &c : t.child)
			output(c, ret);
	}
	else
	{
		ret[t.pic*4+0] = t.y;
		ret[t.pic*4+1] = t.x;
		ret[t.pic*4+2] = t.y+t.h-1;
		ret[t.pic*4+3] = t.x+t.w-1;
	}
}

class CollageMaker{public:
vector<int> compose(vector<int> data)
{
	for (int i=0; i<200; i++)
		used[i] = false;

	int p = 0;
	H = data[p++];
	W = data[p++];
	for (int y=0; y<H; y++)
	for (int x=0; x<W; x++)
		target[y][x] = data[p++];
	
	for (int i=0; i<200; i++)
	{
		PIC &s = source[i];
		s.h = data[p++];
		s.w = data[p++];
		for (int y=0; y<s.h; y++)
		for (int x=0; x<s.w; x++)
			s.data[y][x] = data[p++];
	}

	log("W, H: %d, %d\n", W, H);

	int CS = 64;

	for (int i=0; i<200; i++)
	{
		scale(scaled[0]+i, source+i, CS, CS);
		scale(scaled[1]+i, source+i, W%CS, CS);
		scale(scaled[2]+i, source+i, CS, H%CS);
		scale(scaled[3]+i, source+i, W%CS, H%CS);
	}

	vector<TREE> T;

	for (int cy=0; cy<H; cy+=CS)
	for (int cx=0; cx<W; cx+=CS)
	{
		int cw = min(W-cx, CS);
		int ch = min(H-cy, CS);
		int ci = int(ch!=CS)*2 + int(cw!=CS);

		int score = 0x7fffffff;
		int best;

		for (int i=0; i<200; i++)
		if (!used[i] && scaled[ci][i].w>0)
		{
			int s = 0;
			for (int y=0; y<ch; y++)
			for (int x=0; x<cw; x++)
			{
				int t = (int)scaled[ci][i].data[y][x] - target[cy+y][cx+x];
				s += t*t;
			}
			if (s<score)
			{
				score = s;
				best = i;
			}
		}

		TREE t;
		t.x = cx;
		t.y = cy;
		t.w = cw;
		t.h = ch;
		t.pic = best;
		t.score = score;
		t.squre = true;
		T.push_back(t);
		used[best] = true;
	}

	int score = 0;
	for (TREE &t : T)
		score += calcscore(t);
	log("Step 0: %.10f\n", sqrt((double)score/(W*H)));

	for (int step=1; (CS>>step)>0; step++)
	{
		int cs = CS>>step;
		for (int i=0; i<200; i++)
		{
			scale(scaled[0]+i, source+i, cs, cs);
			scale(scaled[1]+i, source+i, W%cs, cs);
			scale(scaled[2]+i, source+i, cs, H%cs);
			scale(scaled[3]+i, source+i, W%cs, H%cs);
			scale(scaled[4]+i, source+i, cs*2, cs);
			scale(scaled[5]+i, source+i, cs, cs*2);
		}

		for (TREE &t : T)
			split(t, cs, step-1);

		int score = 0;
		for (TREE &t : T)
			score += calcscore(t);
		log("Step %d: %.10f\n", step, sqrt((double)score/(W*H)));
	}

	vector<int> ret(200*4, -1);
	for (TREE &t : T)
		output(t, ret);

	log("Time: %.2f [s]\n", (double)clock()/CLOCKS_PER_SEC);

	return ret;
}};

#if TOPCODER_LOCAL

int main()
{
	int len;
	cin>>len;
	vector<int> data(len);
	for (int i=0; i<len; i++)
		cin>>data[i];

	CollageMaker c;
	vector<int> ret = c.compose(data);

	for (int i=0; i<800; i++)
		cout<<ret[i]<<endl;
}

#endif