Submission #1142188
Source Code Expand
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
using namespace std;
#ifdef DEB
#define dump(x) cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif
template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;
namespace std{
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.fr<<','<<a.sc<<')';
return out;
}
}
//const int INF=5e8;
int h,w,K;
char buf[55][55];
typedef vector<pi> vp;
vector<vp> octo;
set<vp> done;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
void regl(vp& ar){
int mnX=15,mnY=15;
for(auto e:ar){
chmin(mnX,e.sc);
chmin(mnY,e.fr);
}
for(auto& e:ar){
e.fr-=mnY;
e.sc-=mnX;
}
sort(ALL(ar));
ar.erase(unique(ALL(ar)),ar.end());
}
void dfs(vp ever){
regl(ever);
if(done.count(ever)) return;
done.insert(ever);
if(ever.size()==K){
octo.pb(ever);
return;
}
for(auto e:ever){
REP(d,4){
int px=e.sc+dx[d],py=e.fr+dy[d];
vp nxt=ever;
nxt.pb({py,px});
dfs(nxt);
}
}
}
vp ans[1005];
int m;
int m2;
vp ans2[1005];
bool used[55][55];
int prof[55][55][3000];
pair<pi,pair<pi,int> >match[55*55*3000];
int main(){
cin>>h>>w>>K;
REP(i,h) scanf("%s",buf[i]);
dfs({{0,0}});
dump(octo.size());
memset(prof,-1,sizeof(prof));
int cnt=0;
REP(i,h) REP(j,w){
REP(k,octo.size()){
bool fail=false;
int mul=1;
for(auto e:octo[k]){
int px=j+e.sc,py=i+e.fr;
if(px<0 || py<0 || px>=w || py>=h) fail=true;
else mul*=(buf[py][px]-'0');
}
if(!fail && mul>0){
prof[i][j][k]=mul;
match[cnt++]={{mul,mul},{{i,j},k}};
}
}
}
prl;
lint score=-1;
REPN(param,20,1){
REP(i,cnt) match[i].fr.fr=match[i].fr.sc+rand()%param*10;
sort(match,match+cnt);
CLR(used);
reverse(match,match+cnt);
lint sum=0;
m=0;
REP(i,cnt){
int id=match[i].sc.sc,bx=match[i].sc.fr.sc,by=match[i].sc.fr.fr;
bool fail=false;
for(auto e:octo[id]){
int px=bx+e.sc,py=by+e.fr;
assert(px<w && py<h && px>=0 && py>=0);
if(used[py][px]) fail=true;
}
if(!fail){
vp tmp=octo[id];
for(auto& e:tmp) e.fr+=by,e.sc+=bx;
ans[m++]=tmp;
for(auto e:tmp) used[e.fr][e.sc]=1;
assert(tmp.size()==K);
sum+=match[i].fr.sc;
}
}
prl;
dump(param);dump(sum);
dump(cnt);
if(score<sum){
dumpR("HOGE");
score=sum;
m2=m;
REP(i,m) ans2[i]=ans[i];
}
}
dump(score);
cout<<m2<<endl;
REP(i,m2){
for(auto e:ans2[i]) printf("%d %d\n",e.fr+1,e.sc+1);
}
return 0;
}
Submission Info
Submission Time
2017-03-04 22:22:57+0900
Task
A - Multiple Pieces
User
hogloid
Language
C++14 (GCC 5.4.1)
Score
948978
Code Size
3601 Byte
Status
AC
Exec Time
9005 ms
Memory
93056 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:97:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i,h) scanf("%s",buf[i]);
^
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
95976 / 1343058
90035 / 1343058
97802 / 1343058
90249 / 1343058
102731 / 1343058
91720 / 1343058
98285 / 1343058
87634 / 1343058
98907 / 1343058
95639 / 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
7329 ms
84864 KB
subtask_01_02.txt
AC
7936 ms
86912 KB
subtask_01_03.txt
AC
8388 ms
91008 KB
subtask_01_04.txt
AC
8867 ms
93056 KB
subtask_01_05.txt
AC
9005 ms
93056 KB
subtask_01_06.txt
AC
7984 ms
86912 KB
subtask_01_07.txt
AC
8199 ms
88960 KB
subtask_01_08.txt
AC
8223 ms
88960 KB
subtask_01_09.txt
AC
8460 ms
91008 KB
subtask_01_10.txt
AC
7675 ms
86912 KB