Submission #316033

#	Time	Username	Problem	Language	Result	Execution time	Memory
316033		Temmie	Riddick's Cube (IZhO13_riddicks)	C++17	100 / 100	39 ms	384 KiB

riddicks

#include <bits/stdc++.h>
 
int n, m, ans = 100500, g[10][10], a[10];
 
void dfs(int x) {
	
	if(x == m) {
		int gg[6][6], cnt = 0;
		for (int i = 0; i < m; i++) {
			cnt += std::min(a[i], n - a[i]);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				gg[i][j] = g[(i + a[j]) % n][j];
			}
		}
		bool good = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(gg[i][j] != gg[i][0]) {
					good = false;
				}
			}
		}
		if(good) {
			ans = std::min(ans, cnt);
		}
		int count = 0;
		std::map <std::vector <int>, int> mp;
		int z[6][6], dp[6][6];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				std::vector <int> cur;
				for (int k = 0; k < m; k++) {
					cur.push_back(gg[i][(j + k) % m]);
				}
				if(mp.find(cur) == mp.end()) {
					mp[cur] = ++count;
				}
				z[i][j] = mp[cur];
			}
		}
		for (int j = 0; j < m; j++) {
			dp[0][j] = std::min(j, m - j);
		}
		for(int i = 1; i < n; i++) {
			for (int j = 0; j < m; j++) {
				dp[i][j] = 1e9;
			}
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < m; k++) {
					if(z[i][j] == z[i - 1][k]) {
						dp[i][j] = std::min(dp[i][j], dp[i - 1][k] + std::min(j, m - j));
					}
				}
			}
		}
		cnt += *std::min_element(dp[n - 1], dp[n - 1] + m);
		ans = std::min(ans, cnt);
		return;
	}
	
	for (int i = 0; i < n; i++) {
		a[x] = i;
		dfs(x + 1);
	}
	
}
 
int main() {
	//std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", g[i] + j);
		}
	}
	dfs(0);
	//std::cout << ans << "\n";
	printf("%d\n", ans);
	//std::cout.flush(); std::cin >> n;
	
}

Compilation message (stderr)

riddicks.cpp: In function 'int main()':
riddicks.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
riddicks.cpp:76:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |    scanf("%d", g[i] + j);
      |    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100