# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
8433 | ainta | Solve another chuck (kriii2_S) | C++98 | 4 ms | 1732 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 |
---|---|---|---|---|
Fetching results... |