Submission #38864

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38864	2018-01-07T11:41:58 Z	Abelyan	Riddick's Cube (IZhO13_riddicks)	C++14	100 / 100	226 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	13 ms	2016 KB	Output is correct
12	Correct	13 ms	2016 KB	Output is correct
13	Correct	186 ms	2016 KB	Output is correct
14	Correct	193 ms	2016 KB	Output is correct
15	Correct	223 ms	2016 KB	Output is correct
16	Correct	176 ms	2016 KB	Output is correct
17	Correct	173 ms	2016 KB	Output is correct
18	Correct	179 ms	2016 KB	Output is correct
19	Correct	226 ms	2016 KB	Output is correct
20	Correct	169 ms	2016 KB	Output is correct