Cod sursa(job #112337)

Utilizator wefgefAndrei Grigorean wefgef Data 4 decembrie 2007 19:06:27
Problema Grozavesti Scor Ascuns
Compilator cpp Status done
Runda Marime 1.46 kb
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;

#define pb push_back
#define sz(c) int((c).size())
#define mp make_pair
#define x first
#define y second

const int Inf = 0x3f3f3f3f;
const int Nmax = 512;

int N;
int A[Nmax][Nmax];
vector< pair< int, pair<int, int> > > Moves;

void ReadData() {
	freopen("grozavesti.in", "r", stdin);
	freopen("grozavesti.out", "w", stdout);
	
	scanf("%d", &N);
	assert(1 <= N && N <= 300);
	
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j) {
			assert(scanf("%d", &A[i][j]));
			assert(1 <= A[i][j] && A[i][j] <= 1000000);
		}
}

void Change_lines(int a, int b) {
	for (int j = 1; j <= N; ++j)
		swap(A[a][j], A[b][j]);
}

void Change_columns(int a, int b) {
	for (int i = 1; i <= N; ++i)
		swap(A[i][a], A[i][b]);
}

void Solve() {
	for (int k = 1; k <= N; ++k) {
		int best = Inf, lin, col;
		
		for (int i = k; i <= N; ++i)
			for (int j = k; j <= N; ++j)
				if (A[i][j] < best) {
					best = A[i][j];
					lin = i;
					col = j;
				}
		if (lin != k) {
			Moves.pb(mp(0, mp(lin, k)));
			Change_lines(lin, k);
		}
		if (col != k) {
			Moves.pb(mp(1, mp(col, k)));
			Change_columns(col, k);
		}
	}
}

void WriteData() {
	printf("%d\n", sz(Moves));
	for (int i = 0; i < sz(Moves); ++i)
		printf("%c %d %d\n", Moves[i].x ? 'C' : 'L', Moves[i].y.x, Moves[i].y.y);
}

int main() {
	ReadData();
	Solve();
	WriteData();
}