Submission #100645

#	Time	Username	Problem	Language	Result	Execution time	Memory
100645		cki86201	Riddick's Cube (IZhO13_riddicks)	C++11	100 / 100	41 ms	384 KiB

riddicks

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int n, m, X[10][10];
int ar[10];
int ans = 100500;

void dfs(int x) {
	if(x == m) {
		int Y[6][6];
		int cnt = 0;
		rep(i, m) cnt += min(ar[i], n - ar[i]);
		rep(i, n) rep(j, m) Y[i][j] = X[(i+ar[j])%n][j];
		int ok = 1;
		rep(i, n) rep(j, m) if(Y[i][j] != Y[i][0]) ok = 0;
		if(ok) ans = min(ans, cnt);
		map <vector <int>, int> Mx; int cs = 0;
		int Z[6][6], dp[6][6];
		rep(i, n) rep(j, m) {
			vector <int> w;
			rep(k, m) w.pb(Y[i][(j+k)%m]);
			if(Mx.find(w) == Mx.end()) Mx[w] = ++cs;
			Z[i][j] = Mx[w];
		}
		rep(j, m) dp[0][j] = min(j, m-j);
		for(int i=1;i<n;i++) {
			rep(j, m) dp[i][j] = 1e9;
			rep(j, m) rep(k, m) if(Z[i][j] == Z[i-1][k]) {
				dp[i][j] = min(dp[i][j], dp[i-1][k] + min(j, m-j));
			}
		}
		cnt += *min_element(dp[n-1], dp[n-1] + m);
		ans = min(ans, cnt);
		return;
	}
	rep(i, n) {
		ar[x] = i;
		dfs(x + 1);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	rep(i, n) rep(j, m) scanf("%d", X[i] + j);
	dfs(0);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100