Submission #38863

#	Time	Username	Problem	Language	Result	Execution time	Memory
38863		Abelyan	Riddick's Cube (IZhO13_riddicks)	C++14	100 / 100	199 ms	2016 KiB

riddicks

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

int a[5][5],b[5],c[5],d[5][5],qan,mn=INT_MAX;
int n, m;


void check(){
	bool mb = true;
	for (int i = 0; i < n; i++){
		int qur = d[i][0];
		for (int j = 1; j < m; j++){
			if (d[i][j] != qur){
				mb = false;
				break;
			}
		}
		if (!mb) break;
	}
	if (mb){
		if (qan < mn) mn = qan;
		return;
	}
	mb = true;
	for (int j = 0; j < m; j++){
		int qur = d[0][j];
		for (int i = 1; i < n; i++){
			if (d[i][j] != qur){
				mb = false;
				break;
			}
		}
		if (!mb){
			return;
		}
	}
	if (qan < mn) mn = qan;
}

void solve(){
	qan = 0;
	int mnval = INT_MAX;
	for (int i = 0; i < n; i++){
		int val = 0;
		for (int j = 0; j < m; j++){
			val += min(((b[j] + i) % n), n - ((b[j] + i) % n));
		}
		if (val < mnval)mnval = val;
	}
	qan += mnval;
	mnval = INT_MAX;
	for (int i = 0; i < m; i++){
		int val = 0;
		for (int j = 0; j < n; j++){
			val += min(((c[j] + i) % m), m - ((c[j] + i) % m));
		}
		if (val < mnval)mnval = val;
	}
	qan += mnval;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			d[(i + b[j]) % n][(j + c[(i + b[j]) % n]) % m] = a[i][j];
		}
	}
	check();
}

void solve2(int k = 1){
	if (k == n){
		solve();
		return;
	}
	for (int i = 0; i < m; i++){
		c[k] = i;
		solve2(k + 1);
	}
}


void solve1(int k=1){
	if (k == m){
		solve2();
		return;
	}
	for (int i = 0; i < n; i++){
		b[k] = i;
		solve1(k + 1);
	}
}


int main(){
	cin >> n >> m;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> a[i][j];
		}
	}
	solve1();
	if (mn == INT_MAX){
		cout << 100500 << endl;
		return 0;
	}
	cout << mn << endl;
	return 0;
}

• Subtask 1: 100 / 100