oj.uz

Submission #515912

# Submission time Handle Problem Language Result Execution time Memory
515912 2022-01-20T06:13:51 Z Be_dos Riddick's Cube (IZhO13_riddicks) C++17
100 / 100
 466 ms 292 KB 
#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;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 3 ms 204 KB Output is correct
9 Correct 29 ms 280 KB Output is correct
10 Correct 27 ms 280 KB Output is correct
11 Correct 25 ms 204 KB Output is correct
12 Correct 26 ms 204 KB Output is correct
13 Correct 452 ms 268 KB Output is correct
14 Correct 437 ms 268 KB Output is correct
15 Correct 466 ms 272 KB Output is correct
16 Correct 453 ms 204 KB Output is correct
17 Correct 453 ms 268 KB Output is correct
18 Correct 434 ms 268 KB Output is correct
19 Correct 435 ms 272 KB Output is correct
20 Correct 445 ms 272 KB Output is correct