Submission #90473

#	Time	Username	Problem	Language	Result	Execution time	Memory
90473		popovicirobert	Riddick's Cube (IZhO13_riddicks)	C++14	100 / 100	644 ms	916 KiB

riddicks

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

int mat[5][5];

int n, m;
int ans;

void bkt_lin(int lin, int tot) {
    if(lin == n) {
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            int ch = mat[i][0];
            int j;
            for(j = 1; j < m; j++) {
                if(ch != mat[i][j])
                    break;
            }
            if(j == m) {
                cnt++;
            }
        }
        if(cnt == n) {
            ans = min(ans, tot);
            return ;
        }
        cnt = 0;
        for(int i = 0; i < m; i++) {
            int ch = mat[0][i];
            int j;
            for(j = 1; j < n; j++) {
                if(ch != mat[j][i])
                    break;
            }
            if(j == n) {
                cnt++;
            }
        }
        if(cnt == m) {
            ans = min(ans, tot);
        }
    }
    else {
        int aux[5][5];
        memcpy(aux, mat, sizeof(mat));
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < m; j++) {
                mat[lin][j] = aux[lin][(j + i) % m];
            }
            bkt_lin(lin + 1, tot + min(i, m - i));
        }
        memcpy(mat, aux, sizeof(aux));
    }
}

void bkt_col(int col, int tot) {
    if(col == m) {
        bkt_lin(0, tot);
    }
    else {
        int aux[5][5];
        memcpy(aux, mat, sizeof(mat));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                mat[j][col] = aux[(j + i) % n][col];
            }
            bkt_col(col + 1, tot + min(i, n - i));
        }
        memcpy(mat, aux, sizeof(aux));
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            cin >> mat[i][j];
        }
    }
    ans = 100500;
    bkt_col(0, 0);
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 100 / 100