Submission #1151197


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^810893^114514;
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,8){
        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 948411
Code Size 4704 Byte
Status AC
Exec Time 9445 ms
Memory 658900 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 95784 / 1343058 90237 / 1343058 97345 / 1343058 90409 / 1343058 102755 / 1343058 91342 / 1343058 98540 / 1343058 87489 / 1343058 98965 / 1343058 95545 / 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 9333 ms 657236 KB
subtask_01_02.txt AC 9328 ms 658388 KB
subtask_01_03.txt AC 9340 ms 658516 KB
subtask_01_04.txt AC 9336 ms 658132 KB
subtask_01_05.txt AC 9355 ms 658900 KB
subtask_01_06.txt AC 9302 ms 658132 KB
subtask_01_07.txt AC 9301 ms 657492 KB
subtask_01_08.txt AC 9313 ms 658644 KB
subtask_01_09.txt AC 9445 ms 657236 KB
subtask_01_10.txt AC 9312 ms 658516 KB