CodeChef submission 68658 (C++ 4.0.0-8) plaintext list. Status: AC, problem FX, contest AUG09. By gmark (Mark Greve), 2009-08-11 01:20:10.
// Crystals
// Source: CodeChef August 2009 Algorithm Challenge
// CodeChef ID: FX
// Date: 07-08-2009
// Author: Mark Greve
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
typedef long long LL;
typedef pair<int,int> pii;
#define MP make_pair
 
// TIMING CODE
//{{{
#include <sys/time.h>
#include <sys/resource.h>
#include <stdint.h>
#include <time.h>
 
typedef uint_fast64_t test_time_t;
inline void getTestTime(test_time_t &a) {
	struct timeval tv;
	gettimeofday(&tv, NULL);
	a = tv.tv_sec;
	a *= 1000*1000;
	a += tv.tv_usec;
}
inline uint_fast64_t testTimeDiff(const test_time_t& a, const test_time_t& b) {
	return b-a;
}
test_time_t START_TIME; // global start time
//}}}
// END TIMING CODE
 
// FAST IO
//{{{
char *start;
const int MAXBUF=2000000;
char buf[MAXBUF];
char outbuf[MAXBUF];
int outat;
void skip() {
	while (*start != 0  && !('0' <= *start && *start <= '9')) ++start;
}
void GETNUM(int& n){
	skip();
	n=0;
	while ('0' <= *start && *start <= '9') {
		n = n*10 + *start-'0', ++start;
	}
}
void take_input() { // Take input using fast I/O
	int sz=fread(buf, sizeof(char), MAXBUF, stdin);
	buf[sz]=0;
	start=buf;
	outat=0;
}
void outc(char c) { outbuf[outat++] = c; }
void out(int x) {
	char s[100]; int at = 0;
	do { s[at++] = x%10, x/=10; } while(x>0);
	for (int i=at-1;i>=0;--i) outbuf[outat++] = s[i]+'0';
}
void flushoutbuf() { fwrite(outbuf,sizeof(char),outat, stdout), outat=0; }
//}}}
// END FAST IO
 
int n, mana_cost;
 
int SORTBY;
struct E {
	int a,b,c,idx;
	E(int x=0,int y=0, int z=0) : a(x), b(y), c(z) {}
	int prodoth() const {
		switch (SORTBY) {
			case 0: return b*c;
			case 1: return a*c;
			case 2: return a*b;
		}
	}
	int level() const {
		switch (SORTBY)  {
			case 0: return a;
			case 1: return b;
			case 2: return c;
		}
	}
	int& rlevel() {
		switch (SORTBY) {
			case 0: return a;
			case 1: return b;
			case 2: return c;
		}
	}
	int cost() const { return a*b*c; }
};
 
const int MAX=100050;
vector<E*> buckets[MAX];
E v[MAX];
E* tmp[MAX], *tmp2[MAX];
 
// Do a simple bucket sort (on the level)
void level_bucket_sort(E* out[MAX]) {
	int maxv = 0;
	for (int i=0;i<n;++i) maxv = max(maxv, v[i].level());
	for (int i=0;i<=maxv;++i) buckets[i].clear();
	for (int i=0;i<n;++i) buckets[v[i].level()].push_back(&v[i]);
	int cnt = 0;
	for (int i=0;i<=maxv;++i) {
		for (int j=0;j<buckets[i].size();++j) {
			out[cnt] = buckets[i][j];
			++cnt;
		}
	}
}
 
// Do a simple bucket sort (on the prodoth)
void prodoth_bucket_sort(E* out[MAX]) {
	int maxv = 0;
	for (int i=0;i<n;++i) maxv = max(maxv, v[i].prodoth());
	for (int i=0;i<=maxv;++i) buckets[i].clear();
	for (int i=0;i<n;++i) buckets[v[i].prodoth()].push_back(&v[i]);
	int cnt = 0;
	for (int i=0;i<=maxv;++i) {
		for (int j=0;j<buckets[i].size();++j) {
			out[cnt] = buckets[i][j];
			++cnt;
		}
	}
}
 
const int MAXMOVES=6000000;
int moves[MAXMOVES];
int mcnt;
 
void output_sol() {
	out(mcnt/3);
	outc('\n');
	for (int i=0;i<mcnt;i+=3) {
		out(moves[i]+1);
		outc(' ');
		out(moves[i+1]+1);
		outc(' ');
		out(moves[i+2]+1);
		outc('\n');
	}
	flushoutbuf();
}
void do_move(int sortf, int a, int b) {
	moves[mcnt++] = sortf;
	moves[mcnt++] = a;
	moves[mcnt++] = b;
}
void do_swap(int i, int j) {
	swap(v[i].rlevel(), v[j].rlevel());
	v[i].rlevel()++;
	v[j].rlevel()++;
}
 
const int INF=1<<30;
int improve(const E* x, const E* y) {
	if (x==0 || y==0) return -INF;
	int oldcost = x->cost() + y->cost();
	int ncost = x->prodoth() * (y->level()+1) + y->prodoth() * (x->level()+1) + mana_cost;
	return oldcost - ncost;
}
 
int solve(int sortf, int TIMEBOUND) {
	test_time_t a;
	getTestTime(a);
	if (testTimeDiff(START_TIME,a)>=TIMEBOUND) return 0;
 
	::SORTBY = sortf;
	prodoth_bucket_sort(tmp);
	level_bucket_sort(tmp2);
 
 
	for (int i=n-1,k=0;k<n;--i,++k) {
		E* x0 = tmp[i];
		E* x1;
		if (i-1>=0) x1 = tmp[i-1];
 
		E* y0 = tmp2[k];
		E* y1;
		if (k+1<n) y1 = tmp2[k+1];
 
		int imp00 = improve(x0,y0);
		int imp01 = improve(x0,y1);
		int imp10 = improve(x1,y0);
		int imp11 = improve(x1,y1);
		int maxv = max(max(imp00,imp01), max(imp10, imp11));
		if (maxv<=0) continue;
 
		if (imp00==maxv) {
			do_swap(x0->idx,y0->idx);
			do_move(sortf, x0->idx, y0->idx);
		}
		else if (imp01 == maxv) {
			do_swap(x0->idx,y1->idx);
			do_move(sortf, x0->idx, y1->idx);
			swap(tmp2[k],tmp2[k+1]);
		}
		else if (imp10 == maxv) {
			do_swap(x1->idx,y0->idx);
			do_move(sortf, x1->idx, y0->idx);
			swap(tmp[i],tmp[i-1]);
		}
		else if (imp11 == maxv) {
			do_swap(x1->idx,y1->idx);
			do_move(sortf, x1->idx, y1->idx);
			swap(tmp[i],tmp[i-1]);
			swap(tmp2[k],tmp2[k+1]);
		}
 
		if (i&(1<<12)) {
			test_time_t a;
			getTestTime(a);
			if (testTimeDiff(START_TIME,a)>=TIMEBOUND) {
				return 0;
			}
		}
	}
	return 1;
}
 
int items[MAX];
void brute_force(int s, int e) {
	for (int i=s;i<e;++i) {
		for (int j=i+1;j<e;++j) {
			for (int p=0;p<3;++p) {
				SORTBY = p;
				if (improve(&v[i],&v[j])>0) {
					//cerr << "SWAP " << i << " " << j << " and " << p << endl;
					do_swap(v[i].idx, v[j].idx);
					do_move(p, v[i].idx, v[j].idx);
				}
			}
		}
	}
}
 
 
int main() {
	getTestTime(START_TIME);
	take_input();
	GETNUM(n);
	GETNUM(mana_cost);
	for (int i=0;i<n;++i) {
		GETNUM(v[i].a);
		GETNUM(v[i].b);
		GETNUM(v[i].c);
		v[i].idx = i;
	}
 
	mcnt = 0;
 
 
	const int ORDERSZ = 3;
	int order[]={2,0,1};
	const int BOUND = 650000;
	for (int i=0;;++i) {
		// 0.69 worked
		// 0.73 worked
		// 0.76 worked
		// 0.78 worked
		// 0.82 worked
		if (!solve(order[i%ORDERSZ],BOUND)) break;
	}
 
	for (int i=0;i<n;++i) items[i] = i;
	random_shuffle(items,items+n);
 
	const int k = 6;
	for (int j=0;j<n;j+=k) brute_force(j,min(n,j+k));
 
	output_sol();
	//cerr << "MCNT/3 " << mcnt/3 << endl;
	return 0;
}