Submission #1143211


Source Code Expand

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

class Timer{
	private:
		chrono::high_resolution_clock::time_point start_time;
		chrono::high_resolution_clock::time_point elapsed;

	public:
		Timer(){}
		void start() { start_time = chrono::system_clock::now();}
		double get_elapsed(){ 
			elapsed = chrono::system_clock::now();
			return chrono::duration_cast<std::chrono::seconds>(elapsed-start_time).count();
		}
};

const int nmax=15;

struct Polyomino{
	int h,w;
	int mino[nmax][nmax];
	bool operator<(const Polyomino a)const{
		rep(i,nmax)rep(j,nmax) if(mino[i][j]!=a.mino[i][j]) return mino[i][j]<a.mino[i][j];
		return false;
	}
};

set<Polyomino> polyomino[10];

inline void normalize(int &h,int &w,int mino[nmax][nmax]){
	int tmp[nmax][nmax];
	rep(i,nmax)rep(j,nmax) tmp[i][j]=0;

	rep(i,h)rep(j,w) tmp[i][j]=mino[i][j];
	int sh=1,th=h-2,sw=1,tw=w-2;
	rep(i,h)rep(j,w){
		if(tmp[i][j]){
			sh=min(sh,i),sw=min(sw,j);
			th=max(th,i),tw=max(tw,j);
		}
	}

	rep(i,nmax)rep(j,nmax) mino[i][j]=0;
	h=th-sh+1,w=tw-sw+1;
	rep(i,h)rep(j,w) mino[i][j]=tmp[i+sh][j+sw];
}

void init(int limit){
	Polyomino one;
	rep(i,nmax)rep(j,nmax) one.mino[i][j]=0;
	one.w=1,one.h=1,one.mino[0][0]=1;
	polyomino[1].insert(one);

	for(int n=2;n<=limit;++n){
		for(auto &cur:polyomino[n-1]){
			int ext[nmax][nmax];
			rep(i,nmax)rep(j,nmax) ext[i][j]=0;

			rep(i,cur.h)rep(j,cur.w) ext[i+1][j+1]=cur.mino[i][j];
			rep(i,cur.h+2)rep(j,cur.w+2){
				if(ext[i][j]) continue;
				bool add=false;
				if(i-1>=0&&ext[i-1][j]) add=true;
				if(j-1>=0&&ext[i][j-1]) add=true;
				if(i+1<cur.h+2&&ext[i+1][j]) add=true;
				if(j+1<cur.w+2&&ext[i][j+1]) add=true;
				if(add){
					int in[nmax][nmax];
					Polyomino nexts;
					rep(a,nmax)rep(b,nmax) in[a][b]=nexts.mino[a][b]=0;

					ext[i][j]=1;

					rep(a,cur.h+2)rep(b,cur.w+2) in[a][b]=ext[a][b];
					int h=cur.h+2,w=cur.w+2;
					normalize(h,w,in);

					nexts.h=h,nexts.w=w;
					rep(a,h)rep(b,w) nexts.mino[a][b]=in[a][b];
					polyomino[n].insert(nexts);

					ext[i][j]=0;
				}
			}
		}
	}
	return ;
}

mt19937 mt;   
uniform_real_distribution<double> rnd(0.0,1.0);

const int BOARD_SIZE=50;
int H,W,K;
int board[BOARD_SIZE][BOARD_SIZE];

using pii=pair<int,int>;
using State=tuple<ll,vector<pii>>;

void input(){
	cin >> H >> W >> K;
	rep(i,BOARD_SIZE){
		string s;
		cin >> s;
		rep(j,BOARD_SIZE) board[i][j]=s[j]-'0';
	}
}

inline void output(vector<pii> ans){
	const int c=int(ans.size())/8;
	cout << c << endl;
	for(auto &it:ans) cout << it.first+1 << " " << it.second+1 << endl;
	return;
}

inline void output_piece(State piece){
	cerr << get<0>(piece) << endl;
	for(auto &it:get<1>(piece)) cerr << it.first+1 << " " << it.second+1 << endl;
	return;
}

/*
inline ll score(vector<pii> ans){
	const int c=int(ans.size())/8;
	
	ll ret=0LL;
	rep(i,c){
		ll cur=1LL;
		rep(j,8){
			const int y=ans[8*i+j].first,x=ans[8*i+j].second;
			cur=1LL*cur*board[y][x];
		}
		ret+=cur;
	}
	return ret;
}
*/


priority_queue<State> pq;

void enumerate(){
	for(auto &poly:polyomino[8]){
		rep(i,BOARD_SIZE)rep(j,BOARD_SIZE){
			if(i+poly.h>BOARD_SIZE) continue;
			if(j+poly.w>BOARD_SIZE) continue;

			State cur;
			get<0>(cur)=1LL;

			rep(pi,poly.h)rep(pj,poly.w){
				if(poly.mino[pi][pj]==0) continue;
				get<0>(cur)*=board[i+pi][j+pj];
				get<1>(cur).push_back(pii(i+pi,j+pj));
			}

			//cerr << get<0>(cur) << endl;
			if(get<0>(cur)==0) continue;
			pq.push(cur);
		}
	}
}

bool used[BOARD_SIZE][BOARD_SIZE];


int main(void){
	init(8);
	input();

	enumerate();
	vector<pii> ans;
	
	while(!pq.empty()){
		State cur=pq.top(); pq.pop();
		bool ok=true;
		//cerr << get<0>(cur) << endl;
		for(auto &it:get<1>(cur)) if(used[it.first][it.second]) ok=false;

		if(ok){
			for(auto &it:get<1>(cur)){
				used[it.first][it.second]=true;
				ans.push_back(it);
			}
		}
	}

	output(ans);

	return 0;
}

Submission Info

Submission Time
Task A - Multiple Pieces
User Hec
Language C++14 (GCC 5.4.1)
Score 945230
Code Size 5171 Byte
Status AC
Exec Time 4390 ms
Memory 312536 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 95805 / 1343058 90039 / 1343058 97162 / 1343058 89959 / 1343058 101664 / 1343058 91586 / 1343058 97870 / 1343058 87049 / 1343058 98422 / 1343058 95674 / 1343058
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 3742 ms 300252 KB
subtask_01_02.txt AC 3876 ms 298972 KB
subtask_01_03.txt AC 4131 ms 300252 KB
subtask_01_04.txt AC 4305 ms 307544 KB
subtask_01_05.txt AC 4390 ms 312536 KB
subtask_01_06.txt AC 3917 ms 298844 KB
subtask_01_07.txt AC 4021 ms 299996 KB
subtask_01_08.txt AC 4016 ms 299484 KB
subtask_01_09.txt AC 4056 ms 299228 KB
subtask_01_10.txt AC 3818 ms 300508 KB