Submission #92834


Source Code Expand

Copy
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cassert>
using namespace std;
typedef long long ll;

#define REP(i,n) for (int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define FOREQ(i,k,n) for (int i=(k); i<=(int)(n); ++i)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(v) (int)((v).size())
#define MEMSET(v,h) memset((v),(h),sizeof(v))

int H, W;
int post[4][4][2] = 
{
 {{0,0},{1,0},{1,1},{2,0}}
,{{0,2},{0,1},{1,1},{0,0}}
,{{2,0},{1,0},{1,-1},{0,0}}
,{{1,-1},{1,0},{0,0},{1,1}}
};

int A[4][2] =
{{0,0},{0,2},{2,0},{1,-1}};

struct Config {
  int y, x, rot;
};

vector<Config> config[20];
char color[14][14];
char f[14][14];

int ktot[16];

bool ok;
void dfs(int y, int x) {
  if (ok) return;

  if (y==H) {
    ok = 1;
    return;
  }

  if (x==W) {
    dfs(y+1, 0);
    return;
  }

  if (f[y][x]) {
    dfs(y, x+1);
    return;
  }
    // cout<<y<<" "<<x<<endl;

  REP(rot, 4) {
    char tmp[14][14];
    memcpy(tmp, f, sizeof(f));

    int type = 0;
    REP(i, 4) {
      int iy=y+post[rot][i][0];
      int ix=x+post[rot][i][1];
      if (iy<0 || iy>=H || ix<0 || ix>=W || tmp[iy][ix]) goto SKIP;
      if (color[iy][ix] == '#') type |= 1<<i;
      f[iy][ix] = 1;
    }

    Config c;
    c.y = y+A[rot][0];
    c.x = x+A[rot][1];
    c.rot = rot;
    config[type].push_back(c);

    if (SZ(config[type]) <= ktot[type]) {
      dfs(y, x+1);
      if (ok) return;

    }

    config[type].pop_back();

SKIP:
    memcpy(f, tmp, sizeof(f));
  }
}

int kind[200];

int main() {
  while (cin >> H >> W) {
    // if (H>8 || W>8) return 0;

    REP(y, H) cin >> color[y];
    MEMSET(ktot, 0);

    int nop; cin >> nop;
    REP(i, H*W/4) {
      cin >> kind[i];
      kind[i]--;
      ktot[kind[i]]++;
    }
    // REP(i, 16) cout << ktot[i]<<endl;


    MEMSET(f, 0);
    REP(i, 16) config[i].clear();
    ok = 0;

    dfs(0, 0);

    if (!ok) {
      puts("-1");
      continue;
    }
       //REP(i, 16) cout<<SZ(config[i])<<endl;

    REP(i, H*W/4) {
      int k = kind[i];
      //cout<<k<<endl;

      Config c = config[k].back();
      // X Y !!!!
      cout << c.x+1 << " " << c.y+1 << " " << c.rot << endl;
      config[k].pop_back();
    }
  }
}

Submission Info

Submission Time
Task E - 天下一ジグソーパズル
User ir5
Language C++ (G++ 4.6.4)
Score 150
Code Size 2545 Byte
Status AC
Exec Time 32 ms
Memory 820 KB

Judge Result

Set Name small medium large
Score / Max Score 30 / 30 50 / 50 70 / 70
Status
AC × 22
AC × 55
AC × 99
Set Name Test Cases
small small_00_sample_01.txt, small_00_sample_02.txt, small_01_randparse_4_4_00.txt, small_01_randparse_4_4_01.txt, small_01_randparse_4_4_02.txt, small_01_randparse_4_4_03.txt, small_01_randparse_4_4_04.txt, small_01_randparse_4_4_05.txt, small_01_randparse_4_4_06.txt, small_01_randparse_4_4_07.txt, small_01_randparse_4_4_08.txt, small_01_randparse_4_4_09.txt, small_02_randdivide_4_4_00.txt, small_02_randdivide_4_4_01.txt, small_02_randdivide_4_4_02.txt, small_02_randdivide_4_4_03.txt, small_02_randdivide_4_4_04.txt, small_02_randdivide_4_4_05.txt, small_02_randdivide_4_4_06.txt, small_02_randdivide_4_4_07.txt, small_02_randdivide_4_4_08.txt, small_02_randdivide_4_4_09.txt
medium small_00_sample_01.txt, small_00_sample_02.txt, small_01_randparse_4_4_00.txt, small_01_randparse_4_4_01.txt, small_01_randparse_4_4_02.txt, small_01_randparse_4_4_03.txt, small_01_randparse_4_4_04.txt, small_01_randparse_4_4_05.txt, small_01_randparse_4_4_06.txt, small_01_randparse_4_4_07.txt, small_01_randparse_4_4_08.txt, small_01_randparse_4_4_09.txt, small_02_randdivide_4_4_00.txt, small_02_randdivide_4_4_01.txt, small_02_randdivide_4_4_02.txt, small_02_randdivide_4_4_03.txt, small_02_randdivide_4_4_04.txt, small_02_randdivide_4_4_05.txt, small_02_randdivide_4_4_06.txt, small_02_randdivide_4_4_07.txt, small_02_randdivide_4_4_08.txt, small_02_randdivide_4_4_09.txt, medium_00_manual_8_8_01.txt, medium_01_randparse_4_8_00.txt, medium_01_randparse_4_8_01.txt, medium_01_randparse_4_8_02.txt, medium_01_randparse_8_4_00.txt, medium_01_randparse_8_4_01.txt, medium_01_randparse_8_4_02.txt, medium_01_randparse_8_8_00.txt, medium_01_randparse_8_8_01.txt, medium_01_randparse_8_8_02.txt, medium_01_randparse_8_8_03.txt, medium_01_randparse_8_8_04.txt, medium_01_randparse_8_8_05.txt, medium_01_randparse_8_8_06.txt, medium_01_randparse_8_8_07.txt, medium_01_randparse_8_8_08.txt, medium_01_randparse_8_8_09.txt, medium_02_randdivide_4_8_00.txt, medium_02_randdivide_4_8_01.txt, medium_02_randdivide_4_8_02.txt, medium_02_randdivide_8_4_00.txt, medium_02_randdivide_8_4_01.txt, medium_02_randdivide_8_4_02.txt, medium_02_randdivide_8_8_00.txt, medium_02_randdivide_8_8_01.txt, medium_02_randdivide_8_8_02.txt, medium_02_randdivide_8_8_03.txt, medium_02_randdivide_8_8_04.txt, medium_02_randdivide_8_8_05.txt, medium_02_randdivide_8_8_06.txt, medium_02_randdivide_8_8_07.txt, medium_02_randdivide_8_8_08.txt, medium_02_randdivide_8_8_09.txt
large large_01_randparse_12_12_00.txt, large_01_randparse_12_12_01.txt, large_01_randparse_12_12_02.txt, large_01_randparse_12_12_03.txt, large_01_randparse_12_12_04.txt, large_01_randparse_12_12_05.txt, large_01_randparse_12_12_06.txt, large_01_randparse_12_12_07.txt, large_01_randparse_12_12_08.txt, large_01_randparse_12_12_09.txt, large_01_randparse_12_4_00.txt, large_01_randparse_12_4_01.txt, large_01_randparse_12_4_02.txt, large_01_randparse_12_8_00.txt, large_01_randparse_12_8_01.txt, large_01_randparse_12_8_02.txt, large_01_randparse_4_12_00.txt, large_01_randparse_4_12_01.txt, large_01_randparse_4_12_02.txt, large_01_randparse_8_12_00.txt, large_01_randparse_8_12_01.txt, large_01_randparse_8_12_02.txt, large_02_randdivide_12_12_00.txt, large_02_randdivide_12_12_01.txt, large_02_randdivide_12_12_02.txt, large_02_randdivide_12_12_03.txt, large_02_randdivide_12_12_04.txt, large_02_randdivide_12_12_05.txt, large_02_randdivide_12_12_06.txt, large_02_randdivide_12_12_07.txt, large_02_randdivide_12_12_08.txt, large_02_randdivide_12_12_09.txt, large_02_randdivide_12_4_00.txt, large_02_randdivide_12_4_01.txt, large_02_randdivide_12_4_02.txt, large_02_randdivide_12_8_00.txt, large_02_randdivide_12_8_01.txt, large_02_randdivide_12_8_02.txt, large_02_randdivide_4_12_00.txt, large_02_randdivide_4_12_01.txt, large_02_randdivide_4_12_02.txt, large_02_randdivide_8_12_00.txt, large_02_randdivide_8_12_01.txt, large_02_randdivide_8_12_02.txt, medium_00_manual_8_8_01.txt, medium_01_randparse_4_8_00.txt, medium_01_randparse_4_8_01.txt, medium_01_randparse_4_8_02.txt, medium_01_randparse_8_4_00.txt, medium_01_randparse_8_4_01.txt, medium_01_randparse_8_4_02.txt, medium_01_randparse_8_8_00.txt, medium_01_randparse_8_8_01.txt, medium_01_randparse_8_8_02.txt, medium_01_randparse_8_8_03.txt, medium_01_randparse_8_8_04.txt, medium_01_randparse_8_8_05.txt, medium_01_randparse_8_8_06.txt, medium_01_randparse_8_8_07.txt, medium_01_randparse_8_8_08.txt, medium_01_randparse_8_8_09.txt, medium_02_randdivide_4_8_00.txt, medium_02_randdivide_4_8_01.txt, medium_02_randdivide_4_8_02.txt, medium_02_randdivide_8_4_00.txt, medium_02_randdivide_8_4_01.txt, medium_02_randdivide_8_4_02.txt, medium_02_randdivide_8_8_00.txt, medium_02_randdivide_8_8_01.txt, medium_02_randdivide_8_8_02.txt, medium_02_randdivide_8_8_03.txt, medium_02_randdivide_8_8_04.txt, medium_02_randdivide_8_8_05.txt, medium_02_randdivide_8_8_06.txt, medium_02_randdivide_8_8_07.txt, medium_02_randdivide_8_8_08.txt, medium_02_randdivide_8_8_09.txt, small_00_sample_01.txt, small_00_sample_02.txt, small_01_randparse_4_4_00.txt, small_01_randparse_4_4_01.txt, small_01_randparse_4_4_02.txt, small_01_randparse_4_4_03.txt, small_01_randparse_4_4_04.txt, small_01_randparse_4_4_05.txt, small_01_randparse_4_4_06.txt, small_01_randparse_4_4_07.txt, small_01_randparse_4_4_08.txt, small_01_randparse_4_4_09.txt, small_02_randdivide_4_4_00.txt, small_02_randdivide_4_4_01.txt, small_02_randdivide_4_4_02.txt, small_02_randdivide_4_4_03.txt, small_02_randdivide_4_4_04.txt, small_02_randdivide_4_4_05.txt, small_02_randdivide_4_4_06.txt, small_02_randdivide_4_4_07.txt, small_02_randdivide_4_4_08.txt, small_02_randdivide_4_4_09.txt
Case Name Status Exec Time Memory
large_01_randparse_12_12_00.txt AC 22 ms 788 KB
large_01_randparse_12_12_01.txt AC 23 ms 784 KB
large_01_randparse_12_12_02.txt AC 20 ms 812 KB
large_01_randparse_12_12_03.txt AC 22 ms 792 KB
large_01_randparse_12_12_04.txt AC 22 ms 796 KB
large_01_randparse_12_12_05.txt AC 22 ms 788 KB
large_01_randparse_12_12_06.txt AC 26 ms 788 KB
large_01_randparse_12_12_07.txt AC 22 ms 788 KB
large_01_randparse_12_12_08.txt AC 21 ms 700 KB
large_01_randparse_12_12_09.txt AC 21 ms 772 KB
large_01_randparse_12_4_00.txt AC 21 ms 820 KB
large_01_randparse_12_4_01.txt AC 22 ms 784 KB
large_01_randparse_12_4_02.txt AC 21 ms 796 KB
large_01_randparse_12_8_00.txt AC 20 ms 788 KB
large_01_randparse_12_8_01.txt AC 21 ms 688 KB
large_01_randparse_12_8_02.txt AC 21 ms 788 KB
large_01_randparse_4_12_00.txt AC 21 ms 816 KB
large_01_randparse_4_12_01.txt AC 21 ms 800 KB
large_01_randparse_4_12_02.txt AC 20 ms 792 KB
large_01_randparse_8_12_00.txt AC 21 ms 784 KB
large_01_randparse_8_12_01.txt AC 21 ms 800 KB
large_01_randparse_8_12_02.txt AC 21 ms 788 KB
large_02_randdivide_12_12_00.txt AC 21 ms 792 KB
large_02_randdivide_12_12_01.txt AC 20 ms 788 KB
large_02_randdivide_12_12_02.txt AC 20 ms 792 KB
large_02_randdivide_12_12_03.txt AC 20 ms 796 KB
large_02_randdivide_12_12_04.txt AC 20 ms 788 KB
large_02_randdivide_12_12_05.txt AC 21 ms 796 KB
large_02_randdivide_12_12_06.txt AC 32 ms 700 KB
large_02_randdivide_12_12_07.txt AC 21 ms 784 KB
large_02_randdivide_12_12_08.txt AC 21 ms 796 KB
large_02_randdivide_12_12_09.txt AC 21 ms 660 KB
large_02_randdivide_12_4_00.txt AC 19 ms 788 KB
large_02_randdivide_12_4_01.txt AC 20 ms 784 KB
large_02_randdivide_12_4_02.txt AC 21 ms 788 KB
large_02_randdivide_12_8_00.txt AC 21 ms 784 KB
large_02_randdivide_12_8_01.txt AC 20 ms 792 KB
large_02_randdivide_12_8_02.txt AC 22 ms 636 KB
large_02_randdivide_4_12_00.txt AC 19 ms 784 KB
large_02_randdivide_4_12_01.txt AC 19 ms 660 KB
large_02_randdivide_4_12_02.txt AC 19 ms 788 KB
large_02_randdivide_8_12_00.txt AC 20 ms 816 KB
large_02_randdivide_8_12_01.txt AC 21 ms 796 KB
large_02_randdivide_8_12_02.txt AC 20 ms 788 KB
medium_00_manual_8_8_01.txt AC 21 ms 788 KB
medium_01_randparse_4_8_00.txt AC 20 ms 788 KB
medium_01_randparse_4_8_01.txt AC 20 ms 788 KB
medium_01_randparse_4_8_02.txt AC 22 ms 660 KB
medium_01_randparse_8_4_00.txt AC 22 ms 796 KB
medium_01_randparse_8_4_01.txt AC 21 ms 768 KB
medium_01_randparse_8_4_02.txt AC 21 ms 660 KB
medium_01_randparse_8_8_00.txt AC 21 ms 788 KB
medium_01_randparse_8_8_01.txt AC 21 ms 780 KB
medium_01_randparse_8_8_02.txt AC 20 ms 696 KB
medium_01_randparse_8_8_03.txt AC 20 ms 788 KB
medium_01_randparse_8_8_04.txt AC 21 ms 792 KB
medium_01_randparse_8_8_05.txt AC 21 ms 788 KB
medium_01_randparse_8_8_06.txt AC 20 ms 784 KB
medium_01_randparse_8_8_07.txt AC 19 ms 684 KB
medium_01_randparse_8_8_08.txt AC 20 ms 684 KB
medium_01_randparse_8_8_09.txt AC 20 ms 788 KB
medium_02_randdivide_4_8_00.txt AC 19 ms 788 KB
medium_02_randdivide_4_8_01.txt AC 21 ms 792 KB
medium_02_randdivide_4_8_02.txt AC 20 ms 796 KB
medium_02_randdivide_8_4_00.txt AC 21 ms 632 KB
medium_02_randdivide_8_4_01.txt AC 21 ms 816 KB
medium_02_randdivide_8_4_02.txt AC 20 ms 664 KB
medium_02_randdivide_8_8_00.txt AC 20 ms 788 KB
medium_02_randdivide_8_8_01.txt AC 20 ms 792 KB
medium_02_randdivide_8_8_02.txt AC 21 ms 768 KB
medium_02_randdivide_8_8_03.txt AC 21 ms 784 KB
medium_02_randdivide_8_8_04.txt AC 19 ms 664 KB
medium_02_randdivide_8_8_05.txt AC 20 ms 684 KB
medium_02_randdivide_8_8_06.txt AC 20 ms 792 KB
medium_02_randdivide_8_8_07.txt AC 20 ms 656 KB
medium_02_randdivide_8_8_08.txt AC 21 ms 788 KB
medium_02_randdivide_8_8_09.txt AC 20 ms 788 KB
small_00_sample_01.txt AC 21 ms 792 KB
small_00_sample_02.txt AC 20 ms 792 KB
small_01_randparse_4_4_00.txt AC 20 ms 684 KB
small_01_randparse_4_4_01.txt AC 19 ms 784 KB
small_01_randparse_4_4_02.txt AC 19 ms 792 KB
small_01_randparse_4_4_03.txt AC 21 ms 784 KB
small_01_randparse_4_4_04.txt AC 20 ms 792 KB
small_01_randparse_4_4_05.txt AC 19 ms 784 KB
small_01_randparse_4_4_06.txt AC 21 ms 788 KB
small_01_randparse_4_4_07.txt AC 21 ms 816 KB
small_01_randparse_4_4_08.txt AC 21 ms 788 KB
small_01_randparse_4_4_09.txt AC 20 ms 788 KB
small_02_randdivide_4_4_00.txt AC 19 ms 660 KB
small_02_randdivide_4_4_01.txt AC 19 ms 792 KB
small_02_randdivide_4_4_02.txt AC 21 ms 780 KB
small_02_randdivide_4_4_03.txt AC 19 ms 792 KB
small_02_randdivide_4_4_04.txt AC 20 ms 788 KB
small_02_randdivide_4_4_05.txt AC 18 ms 820 KB
small_02_randdivide_4_4_06.txt AC 20 ms 788 KB
small_02_randdivide_4_4_07.txt AC 20 ms 796 KB
small_02_randdivide_4_4_08.txt AC 20 ms 784 KB
small_02_randdivide_4_4_09.txt AC 21 ms 792 KB