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 |
|
|
|
|
|
|
|
|
|
|
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 |