Submission #996547

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
996547	2024-06-10T19:14:26 Z	MilosMilutinovic	Riddick's Cube (IZhO13_riddicks)	C++14	100 / 100	1389 ms	604 KB

riddicks

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  int res = 100500;
  auto ShiftRow = [&](int x) {
    vector<int> v;
    for (int y = 0; y < m; y++) {
      v.push_back(a[x][(y + 1) % m]);
    }
    for (int y = 0; y < m; y++) {
      a[x][y] = v[y];
    }
  }; 
  auto ShiftCol = [&](int y) {
    vector<int> v;
    for (int x = 0; x < n; x++) {
      v.push_back(a[(x + 1) % n][y]);
    }
    for (int x = 0; x < n; x++) {
      a[x][y] = v[x];
    }
  };
  auto Good = [&]() {
    {
      bool ok = true;
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          ok = (ok & (a[i][j] == a[i][0]));
        }
      }
      if (ok) {
        return true;
      }
    }
    {
      bool ok = true;
      for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
          ok = (ok & (a[i][j] == a[0][j]));
        }
      }
      if (ok) {
        return true;
      }
    }
    return false;
  };
  function<void(int, int)> GoX = [&](int x, int cur) {
    if (x == n) {
      if (Good()) {
        res = min(res, cur);
      }
      return;
    }
    for (int i = 0; i < m; i++) {
      GoX(x + 1, cur + min(i, m - i));
      ShiftRow(x);
    }
  };
  function<void(int, int)> GoY = [&](int y, int cur) {
    if (y == m) {
      GoX(0, cur);
      return;
    }
    for (int i = 0; i < n; i++) {
      GoY(y + 1, cur + min(i, n - i));
      ShiftCol(y);
    }
  };
  GoY(0, 0);
  cout << res << '\n';
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	7 ms	348 KB	Output is correct
9	Correct	77 ms	432 KB	Output is correct
10	Correct	66 ms	348 KB	Output is correct
11	Correct	108 ms	348 KB	Output is correct
12	Correct	77 ms	600 KB	Output is correct
13	Correct	1327 ms	348 KB	Output is correct
14	Correct	1244 ms	436 KB	Output is correct
15	Correct	1321 ms	596 KB	Output is correct
16	Correct	1389 ms	436 KB	Output is correct
17	Correct	1261 ms	432 KB	Output is correct
18	Correct	1300 ms	432 KB	Output is correct
19	Correct	1254 ms	348 KB	Output is correct
20	Correct	1279 ms	348 KB	Output is correct