Submission #47575

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
47575	2018-05-05T04:46:05 Z	user202729	Riddick's Cube (IZhO13_riddicks)	C++17	100 / 100	2 ms	872 KB

riddicks

#include<iostream>
#include<vector>
#include<array>
#include<algorithm>

std::vector<int>colShift,rowShift;
std::vector<std::vector<int>>table;
int nRow,nCol,ans=100500;

int colShiftCost;

void btRowShift(int row){
	if(row==nRow){
		// calculate rowShiftCost
		int rowShiftCost=1e9;

		rowShift[0]=0;while(true){
			int thisRowShiftCost=0;
			for(int x:rowShift) // only ~ nRow is enough
				thisRowShiftCost+=std::min(x,nCol-x);
			rowShiftCost=std::min(rowShiftCost,thisRowShiftCost);

			std::transform(rowShift.begin(),nRow+rowShift.begin(),rowShift.begin(),
				[](int x){return (x+1)%nCol;});
			if(rowShift[0]==0)break;
		}

		// optimize for ans
		ans=std::min(ans,colShiftCost+rowShiftCost);
		return;
	}

	for(rowShift[row]=0;rowShift[row]<nCol;++rowShift[row]){
		if(std::equal(table[row].begin(),nCol+table[row].begin(),table[row-1].begin()))
			btRowShift(row+1);

		// next: shift the row [row]
		int temp=table[row][0];
		for(int col=1;col<nCol;++col)
			table[row][col-1]=table[row][col];
		table[row].back()=temp;
	}
}

void btColShift(int col){
	if(col==nCol){
		// calculate colShiftCost
		colShiftCost=1e9;

		colShift[0]=0;while(true){
			int thisColShiftCost=0;
			for(int x:colShift) // only ~ nCol is enough
				thisColShiftCost+=std::min(x,nRow-x);
			colShiftCost=std::min(colShiftCost,thisColShiftCost);

			std::transform(colShift.begin(),nCol+colShift.begin(),colShift.begin(),
				[](int x){return (x+1)%nRow;});
			if(colShift[0]==0)break;
		}

		if(colShiftCost>=ans)return; // can't optimize for (ans) anymore

		// now check for all-row-equal condition
		if(std::all_of(table.begin(),nRow+table.begin(),[](std::vector<int> const& row){
			return std::all_of(++row.begin(),nCol+row.begin(),[&](int x){
				return x==row[0];
			});
		})){ // read: [if] [all_of] the [row]s in the [table] has [all_of] elements [==] the item at [0]
			ans=std::min(ans,colShiftCost);
			return;
		};

		btRowShift(1);
		return;
	}

	for(colShift[col]=0;colShift[col]<nRow;++colShift[col]){
		btColShift(col+1);

		// next: shift the column [col]
		int temp=table[0][col];
		for(int row=1;row<nRow;++row)
			table[row-1][col]=table[row][col];
		table.back()[col]=temp;
	}
}

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	
	std::cin>>nRow>>nCol;
	if(nRow==1||nCol==1){
		std::cout<<"0\n";
		return 0;
	}

	table.resize(nRow);
	for(int r=0;r<nRow;++r){
		table[r].resize(nCol);
		for(int c=0;c<nCol;++c)std::cin>>table[r][c];
	}

	colShift.assign(nCol,0);
	rowShift.assign(nRow,0);
	btColShift(1);
	std::cout<<ans<<'\n';
}

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	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	560 KB	Output is correct
5	Correct	2 ms	560 KB	Output is correct
6	Correct	2 ms	560 KB	Output is correct
7	Correct	2 ms	560 KB	Output is correct
8	Correct	2 ms	560 KB	Output is correct
9	Correct	2 ms	560 KB	Output is correct
10	Correct	2 ms	560 KB	Output is correct
11	Correct	2 ms	592 KB	Output is correct
12	Correct	2 ms	616 KB	Output is correct
13	Correct	2 ms	620 KB	Output is correct
14	Correct	2 ms	712 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	2 ms	740 KB	Output is correct
17	Correct	2 ms	872 KB	Output is correct
18	Correct	2 ms	872 KB	Output is correct
19	Correct	2 ms	872 KB	Output is correct
20	Correct	2 ms	872 KB	Output is correct