Submission #90473

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90473	2018-12-21T19:23:07 Z	popovicirobert	Riddick's Cube (IZhO13_riddicks)	C++14	100 / 100	644 ms	916 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	2 ms	508 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	2 ms	508 KB	Output is correct
6	Correct	2 ms	508 KB	Output is correct
7	Correct	2 ms	640 KB	Output is correct
8	Correct	5 ms	696 KB	Output is correct
9	Correct	34 ms	748 KB	Output is correct
10	Correct	37 ms	748 KB	Output is correct
11	Correct	48 ms	748 KB	Output is correct
12	Correct	42 ms	748 KB	Output is correct
13	Correct	412 ms	828 KB	Output is correct
14	Correct	452 ms	828 KB	Output is correct
15	Correct	644 ms	828 KB	Output is correct
16	Correct	431 ms	828 KB	Output is correct
17	Correct	432 ms	828 KB	Output is correct
18	Correct	433 ms	908 KB	Output is correct
19	Correct	422 ms	908 KB	Output is correct
20	Correct	430 ms	916 KB	Output is correct