Submission #1151182
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int R=50;
const int C=50;
const int K=8;
LL G[52][52];
LL g[52][52];
int used[52][52];
#define CIN_ONLY if(1)
struct cww{cww(){CIN_ONLY{ios::sync_with_stdio(false);cin.tie(0);}
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>inline void chmax(T &l,T r){l=max(l,r);}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
for(auto &it:v)is>>it;
return is;
}
struct INPUT{
INPUT(){
int a,b,c;
cin>>a>>b>>c;
REP(i,52)REP(j,52)g[i][j]=0;
REP(i,50){
string t;
cin>>t;
REP(j,50)g[i+1][j+1]=t[j]-'0';
}
}
}input;
unsigned yy=1145141919;
inline unsigned xorshift(){yy=yy^(yy<<13);yy=yy^(yy>>17);return yy=yy^(yy<<5);}
#define MASK 65535
inline int randInt(){return (int) (xorshift()&MASK);}
std::chrono::high_resolution_clock::time_point now_time;
inline void timer_set() {
using namespace std::chrono;
now_time = high_resolution_clock::now();
}
inline bool time_check(int lim) {
using namespace std::chrono;
auto ed = high_resolution_clock::now();
auto t = ed - now_time;
return(duration_cast<milliseconds>(t).count() < lim);
}
typedef vector<int> V;
typedef vector<V> VV;
struct node{
int r[8];
int c[8];
};
struct piece{
pair<LL,LL> score;
node v;
};
bool operator<(const piece &l,const piece &r){
return l.score<r.score;
}
struct result{
LL score;
vector<node> pos;
};
int dr[]={0,1,0,-1};
int dc[]={1,0,-1,0};
typedef pair<int,int> P;
typedef vector<P> VP;
typedef vector<VP> VVP;
VVP mino;
void initmino(int sz){
mino.pb({P(0,0)});
REP(i,sz){
VVP nxt;
for(auto &it:mino){
REP(r,9)REP(c,9)used[r][c]=0;
for(auto &p:it)used[1+p.fi][1+p.se]=1;
VP ad;
for(auto p:it)REP(d,4){
auto iwi=p;
iwi.fi+=dr[d];
iwi.se+=dc[d];
if(used[1+iwi.fi][1+iwi.se])continue;
used[1+iwi.fi][1+iwi.se]=1;
ad.pb(iwi);
}
for(auto jt:ad){
//cout<<jt.fi<<" "<<jt.se<<endl;
auto nxtset=it;
nxtset.pb(jt);
int x=114514;
int y=114514;
for(auto &c:nxtset){
chmin(x,c.fi);
chmin(y,c.se);
}
for(auto &c:nxtset){
c.fi-=x;
c.se-=y;
}
sort(ALL(nxtset));
nxt.pb(nxtset);
}
}
sort(ALL(nxt));
nxt.erase(unique(ALL(nxt)),nxt.end());
swap(mino,nxt);
}
}
vector<piece> allpiece;
result test(){
for(auto&it:allpiece)it.score.se=randInt();
sort(ALL(allpiece));
reverse(ALL(allpiece));
REP(i,52)REP(j,52)G[i][j]=g[i][j];
result res{0,vector<node>()};
for(auto &it:allpiece){
int ok=1;
REP(k,8)if(G[it.v.r[k]][it.v.c[k]]==0)ok=0;
if(ok){
REP(k,8)G[it.v.r[k]][it.v.c[k]]=0;
res.pos.pb(it.v);
res.score+=it.score.fi;
}
}
return res;
}
int main(){
timer_set();
REP(i,52)REP(j,52)G[i][j]=g[i][j];
initmino(7);
result res{-1,vector<node>()};
FOR(i,1,51){
FOR(j,1,51){
for(auto &it:mino){
int x=0;
int y=0;
REP(k,8){
chmax(x,i+it[k].fi);
chmax(y,j+it[k].se);
}
if(x<=50&&y<=50){
piece p;
p.score.fi=1;
REP(k,8){
p.score.fi*=G[i+it[k].fi][j+it[k].se];
p.v.r[k]=i+it[k].fi;
p.v.c[k]=j+it[k].se;
}
allpiece.pb(p);
}
}
}
}
REP(latte,5){
auto ans=test();
if(ans.score>res.score)res=ans;
}
cout<<res.pos.size()<<endl;
for(auto &ans:res.pos)REP(i,8)cout<<ans.r[i]<<" "<<ans.c[i]<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
btk15049 |
Language |
C++14 (GCC 5.4.1) |
Score |
947122 |
Code Size |
4690 Byte |
Status |
AC |
Exec Time |
6188 ms |
Memory |
659028 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 |
95700 / 1343058 |
89944 / 1343058 |
97594 / 1343058 |
90199 / 1343058 |
102283 / 1343058 |
91283 / 1343058 |
98429 / 1343058 |
87350 / 1343058 |
98752 / 1343058 |
95588 / 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 |
6145 ms |
659028 KB |
subtask_01_02.txt |
AC |
6188 ms |
658516 KB |
subtask_01_03.txt |
AC |
6096 ms |
657364 KB |
subtask_01_04.txt |
AC |
6111 ms |
657108 KB |
subtask_01_05.txt |
AC |
6044 ms |
658132 KB |
subtask_01_06.txt |
AC |
6043 ms |
657236 KB |
subtask_01_07.txt |
AC |
6036 ms |
659028 KB |
subtask_01_08.txt |
AC |
6121 ms |
657620 KB |
subtask_01_09.txt |
AC |
6112 ms |
658132 KB |
subtask_01_10.txt |
AC |
6037 ms |
657620 KB |