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