Submission #515912

#TimeUsernameProblemLanguageResultExecution timeMemory
515912Be_dosRiddick's Cube (IZhO13_riddicks)C++17
100 / 100
466 ms292 KiB
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

int32_t ans = 100'500;
void solve2(int32_t ind, int32_t n, int32_t m, int32_t ans_cur, int32_t** arr) {
    if(ind == n) {
        bool ok = true;
        for(int32_t i = 0; i < n; i++) {
            for(int32_t j = 0; j < m; j++)
                if(arr[i][j] != arr[i][0])
                    ok = false;
        }
        bool ok2 = true;
        for(int32_t i = 0; i < n; i++) {
            for(int32_t j = 0; j < m; j++)
                if(arr[i][j] != arr[0][j])
                    ok2 = false;
        }
        if(ok || ok2)
            ans = std::min(ans, ans_cur);
        return;
    }
    for(int32_t i = 0; i < m; i++) {
        solve2(ind + 1, n, m, ans_cur + std::min(i, m - i), arr);

        int32_t last = arr[ind][0];
        for(int32_t j = 0; j < m - 1; j++)
            arr[ind][j] = arr[ind][j + 1];
        arr[ind][m - 1] = last;
    }
}

void solve1(int32_t ind, int32_t m, int32_t n, int32_t ans_cur, int32_t** arr) {
    if(ind == m) {
        solve2(0, n, m, ans_cur, arr);
        return;
    }

    for(int32_t i = 0; i < n; i++) {
        solve1(ind + 1, m, n, ans_cur + std::min(i, n - i), arr);

        int32_t last = arr[0][ind];
        for(int32_t j = 0; j < n - 1; j++)
            arr[j][ind] = arr[j + 1][ind];
        arr[n - 1][ind] = last;
    }
}

int main() {
    int32_t n, m;
    std::cin >> n >> m;

    int32_t** arr = new int32_t*[n];
    for(int32_t i = 0; i < n; i++) {
        arr[i] = new int32_t[m];
        for(int32_t j = 0; j < m; j++)
            std::cin >> arr[i][j];
            //arr[i][j] = 1;
    }

    solve1(0, m, n, 0, arr);

    std::cout << ans;
    return 0;
}





#Verdict Execution timeMemoryGrader output
Fetching results...