Submission #92653

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92653	2019-01-04T09:33:29 Z	SamAnd	Riddick's Cube (IZhO13_riddicks)	C++17	100 / 100	6 ms	504 KB

riddicks

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=7,INF=100500;

int ans=INF;
int a[N][N];
int b[N][N];
int c[N][N];
int n,m;
int t[N],s[N];
bool stg()
{
	bool z=true,z1=true;
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<m;++j)
		{
			if(c[i][j]!=c[i][0])
				z=false;
		}
	}
	for(int j=0;j<m;++j)
	{
		for(int i=0;i<n;++i)
		{
			if(c[i][j]!=c[0][j])
				z1=false;
		}
	}
	return (z||z1);
}
void ab()
{
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<m;++j)
		{
			b[(i+s[j])%n][j]=a[i][j];
		}
	}
}
void bc()
{
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<m;++j)
		{
			c[i][(j+t[i])%m]=b[i][j];
		}
	}
}
void ubd()
{
	ab();
	bc();
	if(stg())
	{
		int yans=0;
		for(int i=0;i<n;++i)
		{
			yans+=min(t[i],m-t[i]);
		}
		for(int i=0;i<m;++i)
		{
			yans+=min(s[i],n-s[i]);
		}
		ans=min(ans,yans);
	}
}
bool stg1(int x,int r)
{
	int q[N],p[N];
	for(int i=0;i<m;++i)
	{
		q[(i+t[0])%m]=b[0][i];
		p[(i+r)%m]=b[x][i];
	}
	for(int i=0;i<m;++i)
		if(p[i]!=q[i])
			return false;
	return true;
}
void rec(int x,int y)
{
	if(x==n && y==m)
	{
		ubd();
		return;
	}
	if(y!=m)
	{
		for(int i=0;i<n;++i)
		{
			s[y]=i;
			rec(x,y+1);
		}
	}
	else
	{
		if(x==0)
		{
			ab();
			for(int i=0;i<m;++i)
			{
				t[x]=i;
				rec(x+1,y);
			}
		}
		else
		{
			int z=INF,zi;
			for(int i=0;i<m;++i)
			{
				if(stg1(x,i) && min(i,m-i)<z)
				{
					zi=i;
					z=min(i,m-i);
				}
			}
			if(z==INF)
				return;
			t[x]=zi;
			rec(x+1,y);
		}
	}
}
int main()
{
	//freopen("riddicks.in","r",stdin);
	//freopen("riddicks.out","w",stdout);
	///in
	cin>>n>>m;
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			cin>>a[i][j];
	/////
	rec(0,0);
	//out
	cout<<ans<<endl;
//	system("pause");
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	3 ms	256 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	5 ms	256 KB	Output is correct
14	Correct	6 ms	504 KB	Output is correct
15	Correct	5 ms	256 KB	Output is correct
16	Correct	5 ms	256 KB	Output is correct
17	Correct	5 ms	256 KB	Output is correct
18	Correct	5 ms	256 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Correct	5 ms	376 KB	Output is correct