Submission #339475

#	Time	Username	Problem	Language	Result	Execution time	Memory
339475		amunduzbaev	Riddick's Cube (IZhO13_riddicks)	C++14	100 / 100	318 ms	492 KiB

riddicks

/** made by amunduzbaev **/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/rope>

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class tmp> bool umin(tmp& a, const tmp b) {return a > b? a = b, true:false;}
template<class tmp> bool umax(tmp& a, const tmp b) {return a < b? a = b, true:false;}

typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int N = 6;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int n, m, k, ans = 100500, a[N][N];

bool check(){
	bool ok = 1;
	for(int i=0;i<n;i++)
		for(int j=0;j<m-1;j++)
			if(a[i][j] != a[i][j+1]) ok = 0;
	if(ok) return 1;
	for(int i=0;i<m;i++)
		for(int j=0;j<n-1;j++) if(a[j][i] != a[j+1][i]) return 0;
	
	return 1;
}

void rcol(int x){
	int tmp = a[0][x];
	for(int i=0;i<n-1;i++) a[i][x] = a[i+1][x];
	a[n-1][x] = tmp;
	return;
}

void rrow(int x){
	int tmp = a[x][0];
	for(int i=0;i<m-1;i++) a[x][i] = a[x][i+1];
	a[x][m-1] = tmp;
}

void row(int x, int cost){
	if(x == n) {
		if(check()) umin(ans, cost);
		return;
	}
	
	for(int i=0;i<m;i++){
		row(x+1, min(i, m-i) + cost);
		rrow(x);
	}
}

void col(int x, int cost){
	if(x == m){
		row(0, cost);
		return;
	}
	for(int i=0;i<n;i++){
		col(x+1, cost + min(i, n-i));
		rcol(x);
	}
}

void solve(){
	cin>>n>>m;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>a[i][j];
	
	col(0, 0);
	cout<<ans<<"\n";
	
	return;
}


int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

• Subtask 1: 100 / 100