Submission #1400834


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
struct UnionFind{
  vector<int> par;
  vector<int> sizes;
  UnionFind(int n):par(n),sizes(n,1){
    for(int i=0;i<n;i++)par[i] = i;
  }
  int find(int x){
    if(x == par[x])return x;
    return par[x] = find(par[x]);
  }
  void unite(int x,int y){
    x = find(x);y = find(y);
    if(x == y)return;
    if(sizes[x] < sizes[y])swap(x,y);
    par[y] = x;
    sizes[x] += sizes[y];
  }
  bool same(int x,int y){
    return find(x) == find(y);
  }
  int size(int x){
    return sizes[find(x)];
  }
};


int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
class Search{
public:
  int used[51][51];
  int maxpoint;
  vector<int> vx,vy;
  vector<int> bestvx,bestvy;
  vector<string> s;
  Search(vector<string> s){
    maxpoint = -1;
    this->s = s;
  }
  void init(){
    maxpoint = -1;
    vx = vector<int>();
    vy = vector<int>();
    bestvx = vector<int>();
    bestvy = vector<int>();
  }
  void dfs(int y,int x,int d,int point){
    if(d == 8) {
      if(point > maxpoint){
        maxpoint = point;
        bestvx = vx;
        bestvy = vy;
      }
      return;
    }
    for(int i=0;i<4;i++){
      int nx = x + dx[i], ny = y + dy[i];
      if(nx < 0 || ny < 0 || nx >= 50 || ny >= 50)continue;
      if(used[ny][nx] != 0)continue;
      if(s[ny][nx] == '0')continue;
      used[y][x] = 1;
      vx.push_back(x);vy.push_back(y);
      dfs(ny,nx,d+1,point * (s[y][x] - '0'));
      vx.pop_back();vy.pop_back();
      used[y][x] = 0;
    }
  }
  void run(){

    memset(used,0,sizeof(used));
    int col = 1;
    vector<vector<int>> vvx,vvy;
    for(int y=0;y<50;y++){
      for(int x=0;x<50;x++){
        init();
        if(used[y][x] != 0)continue;
        if(s[y][x] == '0')continue;
        dfs(y,x,0,1);

        if(bestvx.size() == 0)continue;
        for(int i=0;i<8;i++){
          used[bestvy[i]][bestvx[i]] = col;
        }
        vvx.push_back(bestvx);
        vvy.push_back(bestvy);
        col++;
      }
    }

    cout << vvx.size() << endl;
    for(int i=0;i<vvx.size();i++){
      for(int j=0;j<8;j++){
        cout << vvy[i][j]+1 << " " << vvx[i][j]+1 << endl;
      }
    }
  }
};

int main(void){
  int H,W,K;
  cin >> H >> W >> K;
  vector<string> s(H);
  for(int i=0;i<H;i++){
    cin >> s[i];
  }

  Search search(s);
  search.run();

  return 0;
}

Submission Info

Submission Time
Task A - Multiple Pieces
User tkzw_21
Language C++14 (GCC 5.4.1)
Score 158925
Code Size 2427 Byte
Status AC
Exec Time 6 ms
Memory 256 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 16134 / 1343058 13716 / 1343058 16513 / 1343058 12076 / 1343058 16095 / 1343058 16865 / 1343058 18418 / 1343058 14467 / 1343058 18264 / 1343058 16377 / 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 6 ms 256 KB
subtask_01_02.txt AC 6 ms 256 KB
subtask_01_03.txt AC 6 ms 256 KB
subtask_01_04.txt AC 6 ms 256 KB
subtask_01_05.txt AC 6 ms 256 KB
subtask_01_06.txt AC 6 ms 256 KB
subtask_01_07.txt AC 6 ms 256 KB
subtask_01_08.txt AC 6 ms 256 KB
subtask_01_09.txt AC 6 ms 256 KB
subtask_01_10.txt AC 6 ms 256 KB