Submission #38865

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38865	2018-01-07T11:43:11 Z	Abelyan	Riddick's Cube (IZhO13_riddicks)	C++14	100 / 100	186 ms	2016 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2016 KB	Output is correct
2	Correct	0 ms	2016 KB	Output is correct
3	Correct	0 ms	2016 KB	Output is correct
4	Correct	0 ms	2016 KB	Output is correct
5	Correct	0 ms	2016 KB	Output is correct
6	Correct	0 ms	2016 KB	Output is correct
7	Correct	0 ms	2016 KB	Output is correct
8	Correct	0 ms	2016 KB	Output is correct
9	Correct	9 ms	2016 KB	Output is correct
10	Correct	9 ms	2016 KB	Output is correct
11	Correct	9 ms	2016 KB	Output is correct
12	Correct	9 ms	2016 KB	Output is correct
13	Correct	169 ms	2016 KB	Output is correct
14	Correct	173 ms	2016 KB	Output is correct
15	Correct	169 ms	2016 KB	Output is correct
16	Correct	166 ms	2016 KB	Output is correct
17	Correct	166 ms	2016 KB	Output is correct
18	Correct	166 ms	2016 KB	Output is correct
19	Correct	186 ms	2016 KB	Output is correct
20	Correct	173 ms	2016 KB	Output is correct