oj.uz

Submission #804001

# Submission time Handle Problem Language Result Execution time Memory
804001 2023-08-03T06:49:42 Z 반딧불(#10100) Shifty Grid (CCO17_shifty) C++17
0 / 25
 2000 ms 2060 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
int arr[102][102];
int idxX[10002], idxY[10002];

struct dat{
    int a, b, c;
    dat(){}
    dat(int a, int b, int c): a(a), b(b), c(c){}
};
vector<dat> ans;

int tmp[102];

void rotateRow(int i, int c){
    for(int j=0; j<m; j++) tmp[j] = arr[i][j];
    for(int j=0; j<m; j++){
        arr[i][j] = tmp[(j+m-c)%m];
        idxX[arr[i][j]] = i, idxY[arr[i][j]] = j;
    }
    ans.push_back(dat(1, i, c));
}

void rotateColumn(int j, int c){
    for(int i=0; i<n; i++) tmp[i] = arr[i][j];
    for(int i=0; i<n; i++){
        arr[i][j] = tmp[(i+n-c)%n];
        idxX[arr[i][j]] = i, idxY[arr[i][j]] = j;
    }
    ans.push_back(dat(2, j, c));
}
const int LIM = 2;
vector<dat> vec;
void backtrack(int turns){
    int rcnt = 0, ccnt = 0;

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++) if(arr[i][j] / m != i) {rcnt++; break;}
    }
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++) if(arr[j][i] % m != i) {ccnt++; break;}
    }

    if(!rcnt && !ccnt){
        printf("%d\n", (int)vec.size());
        for(dat p: vec) printf("%d %d %d\n", p.a, p.b+1, p.c);
        exit(0);
    }

    if(min(rcnt, ccnt) + turns >= LIM+1) return;

    for(int i=0; i<n; i++){
        for(int j=1; j<m; j++){
            vec.push_back(dat(1, i, j));
            rotateRow(i, j);
            backtrack(turns+1);
            rotateRow(i, m-j);
            vec.pop_back();
        }
    }
    for(int i=0; i<m; i++){
        for(int j=1; j<n; j++){
            vec.push_back(dat(2, i, j));
            rotateColumn(i, j);
            backtrack(turns+1);
            rotateColumn(i, n-j);
            vec.pop_back();
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &arr[i][j]);
            idxX[arr[i][j]] = i, idxY[arr[i][j]] = j;
        }
    }

    backtrack(0);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:81:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |             scanf("%d", &arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Execution timed out 2079 ms 2060 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -