Submission #92491


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 ret = 0;
int w, h;
int f[40][40];
void dfs(int y, int x) {
  if (x==w) { dfs(y+1,0); return; }
  if (y==h) { ret++; return; }

  FOREQ(t, 1, 3) {
    f[y][x]=t;

    FOREQ(k, max(0, y-t), y-1) if (f[k][x] == t) goto SKIP;
    FOREQ(k, max(0, x-t), x-1) if (f[y][k] == t) goto SKIP;
    dfs(y, x+1);
SKIP:;
  }
}

int got(int W, int H) {
  if (W<=10 && H<=10) {
    w=W, h=H;
    ret=0;
    dfs(0,0);
    return ret;
  }
  if (W==1) swap(W, H);
  if (H==1) {
    if (W%4==0) return 10;
    if (W%4==1) return 9 ;
    if (W%4==2) return 8 ;
    if (W%4==3) return 9 ;
  }

  if ((W+H)%2==0) return 18;
  if ((W+H)%4==1) return 20;
  if ((W+H)%4==3) return 16;

  return -1;
}

int main() {
  /*
  FOREQ(w, 1, 30) {
    FOREQ(h, 1, 30) {
      W=w, H=h;
      ret=0;
      dfs(0,0);
      printf(" ");
      if (ret<10) printf(" ");
      printf("%d", ret);
    }
    cout<<endl;
  }
  */
  int W,H;
  cin >> W >> H;
  cout << got(W, H) << endl; 


}

Submission Info

Submission Time
Task C - 天下一二三パズル
User ir5
Language C++ (G++ 4.6.4)
Score 120
Code Size 1625 Byte
Status AC
Exec Time 24 ms
Memory 820 KB

Judge Result

Set Name small medium large
Score / Max Score 40 / 40 20 / 20 60 / 60
Status
AC × 18
AC × 72
AC × 118
Set Name Test Cases
small small, small/00_manual1, small/00_manual2, small/01_small_0, small/01_small_1, small/01_small_10, small/01_small_11, small/01_small_12, small/01_small_13, small/01_small_14, small/01_small_15, small/01_small_2, small/01_small_3, small/01_small_4, small/01_small_5, small/01_small_6, small/01_small_7, small/01_small_8, small/01_small_9
medium small, small/00_manual1, small/00_manual2, small/01_small_0, small/01_small_1, small/01_small_10, small/01_small_11, small/01_small_12, small/01_small_13, small/01_small_14, small/01_small_15, small/01_small_2, small/01_small_3, small/01_small_4, small/01_small_5, small/01_small_6, small/01_small_7, small/01_small_8, small/01_small_9, medium, medium/02_00_middle_0, medium/02_00_middle_1, medium/02_00_middle_10, medium/02_00_middle_11, medium/02_00_middle_12, medium/02_00_middle_13, medium/02_00_middle_14, medium/02_00_middle_15, medium/02_00_middle_16, medium/02_00_middle_17, medium/02_00_middle_18, medium/02_00_middle_19, medium/02_00_middle_2, medium/02_00_middle_20, medium/02_00_middle_21, medium/02_00_middle_22, medium/02_00_middle_23, medium/02_00_middle_24, medium/02_00_middle_25, medium/02_00_middle_26, medium/02_00_middle_27, medium/02_00_middle_28, medium/02_00_middle_29, medium/02_00_middle_3, medium/02_00_middle_30, medium/02_00_middle_31, medium/02_00_middle_32, medium/02_00_middle_33, medium/02_00_middle_34, medium/02_00_middle_35, medium/02_00_middle_36, medium/02_00_middle_37, medium/02_00_middle_38, medium/02_00_middle_39, medium/02_00_middle_4, medium/02_00_middle_40, medium/02_00_middle_41, medium/02_00_middle_42, medium/02_00_middle_43, medium/02_00_middle_44, medium/02_00_middle_45, medium/02_00_middle_46, medium/02_00_middle_47, medium/02_00_middle_48, medium/02_00_middle_49, medium/02_00_middle_5, medium/02_00_middle_6, medium/02_00_middle_7, medium/02_00_middle_8, medium/02_00_middle_9, medium/02_01_middle_random_0, medium/02_01_middle_random_1, medium/02_01_middle_random_2, medium/02_01_middle_random_3
large large, medium, small, large/03_00_big_0, large/03_00_big_1, large/03_00_big_10, large/03_00_big_11, large/03_00_big_12, large/03_00_big_13, large/03_00_big_14, large/03_00_big_15, large/03_00_big_16, large/03_00_big_17, large/03_00_big_18, large/03_00_big_19, large/03_00_big_2, large/03_00_big_20, large/03_00_big_21, large/03_00_big_22, large/03_00_big_23, large/03_00_big_24, large/03_00_big_25, large/03_00_big_26, large/03_00_big_27, large/03_00_big_28, large/03_00_big_29, large/03_00_big_3, large/03_00_big_30, large/03_00_big_31, large/03_00_big_32, large/03_00_big_33, large/03_00_big_34, large/03_00_big_35, large/03_00_big_36, large/03_00_big_37, large/03_00_big_38, large/03_00_big_39, large/03_00_big_4, large/03_00_big_5, large/03_00_big_6, large/03_00_big_7, large/03_00_big_8, large/03_00_big_9, large/03_01_big_random_0, large/03_01_big_random_1, large/03_01_big_random_2, large/03_01_big_random_3, large/03_01_big_random_4, large/03_01_big_random_5, medium/02_00_middle_0, medium/02_00_middle_1, medium/02_00_middle_10, medium/02_00_middle_11, medium/02_00_middle_12, medium/02_00_middle_13, medium/02_00_middle_14, medium/02_00_middle_15, medium/02_00_middle_16, medium/02_00_middle_17, medium/02_00_middle_18, medium/02_00_middle_19, medium/02_00_middle_2, medium/02_00_middle_20, medium/02_00_middle_21, medium/02_00_middle_22, medium/02_00_middle_23, medium/02_00_middle_24, medium/02_00_middle_25, medium/02_00_middle_26, medium/02_00_middle_27, medium/02_00_middle_28, medium/02_00_middle_29, medium/02_00_middle_3, medium/02_00_middle_30, medium/02_00_middle_31, medium/02_00_middle_32, medium/02_00_middle_33, medium/02_00_middle_34, medium/02_00_middle_35, medium/02_00_middle_36, medium/02_00_middle_37, medium/02_00_middle_38, medium/02_00_middle_39, medium/02_00_middle_4, medium/02_00_middle_40, medium/02_00_middle_41, medium/02_00_middle_42, medium/02_00_middle_43, medium/02_00_middle_44, medium/02_00_middle_45, medium/02_00_middle_46, medium/02_00_middle_47, medium/02_00_middle_48, medium/02_00_middle_49, medium/02_00_middle_5, medium/02_00_middle_6, medium/02_00_middle_7, medium/02_00_middle_8, medium/02_00_middle_9, medium/02_01_middle_random_0, medium/02_01_middle_random_1, medium/02_01_middle_random_2, medium/02_01_middle_random_3, small/00_manual1, small/00_manual2, small/01_small_0, small/01_small_1, small/01_small_10, small/01_small_11, small/01_small_12, small/01_small_13, small/01_small_14, small/01_small_15, small/01_small_2, small/01_small_3, small/01_small_4, small/01_small_5, small/01_small_6, small/01_small_7, small/01_small_8, small/01_small_9
Case Name Status Exec Time Memory
large/03_00_big_0 AC 20 ms 784 KB
large/03_00_big_1 AC 21 ms 788 KB
large/03_00_big_10 AC 19 ms 792 KB
large/03_00_big_11 AC 23 ms 652 KB
large/03_00_big_12 AC 19 ms 792 KB
large/03_00_big_13 AC 19 ms 800 KB
large/03_00_big_14 AC 20 ms 688 KB
large/03_00_big_15 AC 19 ms 792 KB
large/03_00_big_16 AC 18 ms 792 KB
large/03_00_big_17 AC 18 ms 788 KB
large/03_00_big_18 AC 21 ms 796 KB
large/03_00_big_19 AC 20 ms 796 KB
large/03_00_big_2 AC 19 ms 780 KB
large/03_00_big_20 AC 18 ms 788 KB
large/03_00_big_21 AC 18 ms 688 KB
large/03_00_big_22 AC 20 ms 788 KB
large/03_00_big_23 AC 19 ms 788 KB
large/03_00_big_24 AC 20 ms 784 KB
large/03_00_big_25 AC 19 ms 792 KB
large/03_00_big_26 AC 20 ms 784 KB
large/03_00_big_27 AC 19 ms 792 KB
large/03_00_big_28 AC 19 ms 784 KB
large/03_00_big_29 AC 19 ms 788 KB
large/03_00_big_3 AC 20 ms 692 KB
large/03_00_big_30 AC 19 ms 636 KB
large/03_00_big_31 AC 20 ms 764 KB
large/03_00_big_32 AC 23 ms 784 KB
large/03_00_big_33 AC 24 ms 660 KB
large/03_00_big_34 AC 22 ms 656 KB
large/03_00_big_35 AC 24 ms 652 KB
large/03_00_big_36 AC 21 ms 768 KB
large/03_00_big_37 AC 21 ms 688 KB
large/03_00_big_38 AC 20 ms 808 KB
large/03_00_big_39 AC 19 ms 792 KB
large/03_00_big_4 AC 19 ms 784 KB
large/03_00_big_5 AC 20 ms 696 KB
large/03_00_big_6 AC 21 ms 792 KB
large/03_00_big_7 AC 19 ms 788 KB
large/03_00_big_8 AC 20 ms 788 KB
large/03_00_big_9 AC 20 ms 780 KB
large/03_01_big_random_0 AC 19 ms 792 KB
large/03_01_big_random_1 AC 20 ms 772 KB
large/03_01_big_random_2 AC 21 ms 796 KB
large/03_01_big_random_3 AC 19 ms 788 KB
large/03_01_big_random_4 AC 23 ms 784 KB
large/03_01_big_random_5 AC 19 ms 788 KB
medium/02_00_middle_0 AC 21 ms 784 KB
medium/02_00_middle_1 AC 21 ms 664 KB
medium/02_00_middle_10 AC 19 ms 792 KB
medium/02_00_middle_11 AC 21 ms 788 KB
medium/02_00_middle_12 AC 20 ms 792 KB
medium/02_00_middle_13 AC 18 ms 784 KB
medium/02_00_middle_14 AC 19 ms 792 KB
medium/02_00_middle_15 AC 21 ms 632 KB
medium/02_00_middle_16 AC 20 ms 784 KB
medium/02_00_middle_17 AC 20 ms 788 KB
medium/02_00_middle_18 AC 21 ms 660 KB
medium/02_00_middle_19 AC 21 ms 792 KB
medium/02_00_middle_2 AC 21 ms 780 KB
medium/02_00_middle_20 AC 21 ms 796 KB
medium/02_00_middle_21 AC 19 ms 784 KB
medium/02_00_middle_22 AC 22 ms 788 KB
medium/02_00_middle_23 AC 21 ms 780 KB
medium/02_00_middle_24 AC 20 ms 788 KB
medium/02_00_middle_25 AC 19 ms 780 KB
medium/02_00_middle_26 AC 19 ms 792 KB
medium/02_00_middle_27 AC 21 ms 692 KB
medium/02_00_middle_28 AC 20 ms 784 KB
medium/02_00_middle_29 AC 21 ms 784 KB
medium/02_00_middle_3 AC 18 ms 788 KB
medium/02_00_middle_30 AC 18 ms 792 KB
medium/02_00_middle_31 AC 21 ms 796 KB
medium/02_00_middle_32 AC 21 ms 780 KB
medium/02_00_middle_33 AC 21 ms 780 KB
medium/02_00_middle_34 AC 21 ms 796 KB
medium/02_00_middle_35 AC 19 ms 692 KB
medium/02_00_middle_36 AC 19 ms 788 KB
medium/02_00_middle_37 AC 20 ms 788 KB
medium/02_00_middle_38 AC 20 ms 784 KB
medium/02_00_middle_39 AC 21 ms 812 KB
medium/02_00_middle_4 AC 20 ms 792 KB
medium/02_00_middle_40 AC 20 ms 792 KB
medium/02_00_middle_41 AC 18 ms 780 KB
medium/02_00_middle_42 AC 19 ms 784 KB
medium/02_00_middle_43 AC 19 ms 784 KB
medium/02_00_middle_44 AC 18 ms 792 KB
medium/02_00_middle_45 AC 20 ms 668 KB
medium/02_00_middle_46 AC 20 ms 788 KB
medium/02_00_middle_47 AC 20 ms 784 KB
medium/02_00_middle_48 AC 19 ms 676 KB
medium/02_00_middle_49 AC 21 ms 624 KB
medium/02_00_middle_5 AC 20 ms 784 KB
medium/02_00_middle_6 AC 20 ms 784 KB
medium/02_00_middle_7 AC 22 ms 780 KB
medium/02_00_middle_8 AC 19 ms 788 KB
medium/02_00_middle_9 AC 19 ms 784 KB
medium/02_01_middle_random_0 AC 20 ms 788 KB
medium/02_01_middle_random_1 AC 19 ms 788 KB
medium/02_01_middle_random_2 AC 21 ms 820 KB
medium/02_01_middle_random_3 AC 19 ms 784 KB
small/00_manual1 AC 18 ms 788 KB
small/00_manual2 AC 20 ms 692 KB
small/01_small_0 AC 21 ms 788 KB
small/01_small_1 AC 21 ms 816 KB
small/01_small_10 AC 20 ms 780 KB
small/01_small_11 AC 21 ms 788 KB
small/01_small_12 AC 21 ms 696 KB
small/01_small_13 AC 20 ms 660 KB
small/01_small_14 AC 20 ms 784 KB
small/01_small_15 AC 19 ms 688 KB
small/01_small_2 AC 21 ms 788 KB
small/01_small_3 AC 20 ms 792 KB
small/01_small_4 AC 20 ms 792 KB
small/01_small_5 AC 19 ms 788 KB
small/01_small_6 AC 21 ms 640 KB
small/01_small_7 AC 21 ms 792 KB
small/01_small_8 AC 20 ms 796 KB
small/01_small_9 AC 21 ms 796 KB