Submission #8433

#	Time	Username	Problem	Language	Result	Execution time	Memory
8433		ainta	Solve another chuck (kriii2_S)	C++98	4 / 4	4 ms	1732 KiB

S

#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
using namespace std;
bool Neg[110][110], chk, Com[110], TNeg[110];
int n, m, w[110][110], Tw[110], cnt;
struct Answer{
	int ck, x, d;
}Res[50010];
void Ins(int ck, int x, int d){
	Res[cnt].ck = ck;
	Res[cnt].x = x;
	Res[cnt].d = d;
	cnt++;
}
void Move(bool ck, int x, int d){
	int i;
	if (!ck){
		d %= m;
		for (i = m - d + 1; i <= m; i++){
			Tw[i - m + d] = w[x][i];
			TNeg[i - m + d] = Neg[x][i];
		}
		for (i = m; i != d; i--){
			w[x][i] = w[x][i - d];
			Neg[x][i] = Neg[x][i - d];
		}
		for (i = 1; i <= d; i++){
			w[x][i] = Tw[i];
			Neg[x][i] = TNeg[i];
		}
	}
	else{
		d %= n;
		for (i = n - d + 1; i <= n; i++){
			Tw[i - n + d] = w[i][x];
			TNeg[i - n + d] = Neg[i][x];
		}
		for (i = n; i != d; i--){
			w[i][x] = w[i - d][x];
			Neg[i][x] = Neg[i - d][x];
		}
		for (i = 1; i <= d; i++){
			w[i][x] = Tw[i];
			Neg[i][x] = TNeg[i];
		}
	}
	if (!d)return;
	Ins(chk == ck ? 1 : 2, x, d);
}
void Inv(bool ck, int x){
	Ins(chk == ck ? 3 : 4, x, -1);
	int i;
	if (!ck){
		for (i = 1; i <= m; i++)Neg[x][i] = !Neg[x][i];
	}
	else{
		for (i = 1; i <= n; i++)Neg[i][x] = !Neg[i][x];
	}
}
void Do1(){
	int i, j, x, c;
	while (1){
		c = 0;
		for (i = 1; i <= n; i++){
			for (j = 1; j <= m; j++){
				if (Neg[i][j])break;
			}
			if (j == m + 1)Com[i] = true;
			if (Com[i])continue;
			x = j;
			Move(0, i, m + 1 - x);
			c++;
		}
		if (!c)break;
		Inv(1, 1);
	}
}
void Do2(){
	int i, j, c = 0;
	for (i = 1; i <= n; i++){
		if (Neg[i][1])c++;
	}
	if (!c)return;
	if (c % 2 == 1){
		Inv(1, 1);
		c = n - c;
	}
	c /= 2;
	for (i = 1; i <= n; i++){
		if (c && Neg[i][1]){
			Move(0, i, 1);
			c--;
		}
	}
	Inv(1, 1);
	for (i = 1; i <= n; i++){
		for (j = 1; j <= n; j++){
			if (Neg[j][1] && !Neg[j][2]){
				Move(0, j, 1);
			}
		}
		Move(1, 1, 1);
	}
	Inv(1, 2);
}
int Mini = 99999, SS = 0, NC = 0;
void MvX(int x, int y){
	Inv(0, x);
	Move(1, y, n - 1);
	Inv(0, x);
	Move(1, y, 1);
}
void MvY(int x, int y){
	Inv(1, y);
	Move(0, x, m - 1);
	Inv(1, y);
	Move(0, x, 1);
}
void Do3()
{
	int i, j, sx, sy, ex, ey;
	for (i = 1; i <= n; i++){
		for (j = 1; j <= m; j++){
			if (Neg[i][j])sx = i, sy = j;
			if (Mini == w[i][j])ex = i, ey = j;
		}
	}
	while (sx != ex){
		MvX(sx, sy);
		sx = sx%n + 1;
	}
	while (sy != ey){
		MvY(sx, sy);
		sy = sy%m + 1;
	}
}
int main()
{
	int i, j;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++){
		for (j = 1; j <= m; j++){
			scanf("%d", &w[i][j]);
			if (w[i][j] < 0){
				NC++;
				Neg[i][j] = true;
				w[i][j] = -w[i][j];
			}
			if (Mini>w[i][j])Mini = w[i][j];
			SS += w[i][j];
		}
	}
	if (n % 2 == 0 && m % 2 == 1){
		chk = true;
		swap(n, m);
		for (i = 1; i <= 100; i++){
			for (j = i + 1; j <= 100; j++){
				swap(w[i][j], w[j][i]);
				swap(Neg[i][j], Neg[j][i]);
			}
		}
	}
	if (m == 1){
		for (i = 1; i <= n; i++){
			if (Neg[i][1])Inv(0, i);
		}
	}
	else{
		Do1();
		Do2();
		if (n % 2 == 0 && m % 2 == 0 && NC % 2 == 1){
			Do3();
			SS -= Mini * 2;
		}
	}
	printf("%d %d\n", SS, cnt);
	for (i = 0; i < cnt; i++){
		if (Res[i].ck <= 2){
			printf(Res[i].ck == 1 ? "rotR" : "rotC");
			printf(" %d %d\n", Res[i].x, Res[i].d);
		}
		else{
			printf(Res[i].ck == 3 ? "negR" : "negC");
			printf(" %d\n", Res[i].x);
		}
	}
	return 0;
}

• Subtask 1: 4 / 4