#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1732 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 20 |
Correct |
4 ms |
1732 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 22 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 23 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 24 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 25 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 26 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 27 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 28 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 29 |
Correct |
0 ms |
1732 KB |
Output is correct |
| 30 |
Correct |
0 ms |
1732 KB |
Output is correct |
