Submission #984370


Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;

public class Main {
  HashMap<Integer, Integer> map;
  int[] dp;

  void run() {
    map = new HashMap<>();
    for (int i = 0; i < 5; ++i) {
      for (int j = 0; j < 5; ++j) {
        int x = ni();
        if (x > 0) {
          map.put(x, i * 5 + j);
        }
      }
    }
//    dp = new int[1 << 25];
//    dp[0] = 1;
//    TreeSet<Pair<Integer, Integer>> queue = new TreeSet<>();
//    queue.add(new Pair<>(0, 1));
//    while (queue.size() > 0) {
//      Pair<Integer, Integer> v = queue.first();
//      queue.remove(v);
//      int i = v.f;
//      int num = v.s;
//      if (map.containsKey(num)) { // 指定されている場合
//        int p = map.get(num);
//        if (((i >> p) & 1) == 0 && f(i, p)) { // すでに置かれてなかったら遷移
//          dp[i | 1 << p] += dp[i];
//          dp[i | 1 << p] %= MOD;
//          Pair<Integer, Integer> next = new Pair<>(i | 1 << p, num + 1);
//          if (!queue.contains(next)) {
//            queue.add(next);
//          }
//        }
//      } else {
//        for (int j = 0; j < 25; ++j) {
//          if (((i >> j) & 1) != 0) {
//            continue;
//          }
//          if (f(i, j)) {
//            dp[i | 1 << j] += dp[i];
//            dp[i | 1 << j] %= MOD;
//            Pair<Integer, Integer> next = new Pair<>(i | 1 << j, num + 1);
//            if (!queue.contains(next)) {
//              queue.add(next);
//            }
//          }
//        }
//      }
//    }

    System.out.println(dfs((1 << 25) - 1, 25));
  }

  boolean[] done = new boolean[1 << 25];
  int[] memo = new int[1 << 25];

  int dfs(int i, int num) {
    if (num == 0) {
      return 1;
    }
    if (done[i]) {
      return memo[i];
    }
    if (map.containsKey(num)) {
      int p = map.get(num);
      if (((i >> p) & 1) == 1) {
        int prev = i - (1 << p);
        if (f(prev, p)) {
          done[i] = true;
          return memo[i] = dfs(prev, num - 1);
        }
      }
      return 0;
    } else {
      int sum = 0;
      for (int j = 0; j < 25; ++j) {
        if (((i >> j) & 1) == 1) {
          int prev = i - (1 << j);
          if (f(prev, j)) {
            sum += dfs(prev, num - 1);
            sum %= MOD;
          }
        }
      }
      done[i] = true;
      memo[i] = sum;
      return sum;
    }
  }

  boolean f(int bits, int next) {
    boolean yoko = false;
    {
      int h = next - 1;
      int m = next + 1;
      if (0 <= h && h / 5 == next / 5 && m / 5 == next / 5) {
        if ((((bits >> h) & 1) ^ ((bits >> m) & 1)) == 1) {
          yoko = true;
        }
      }
    }
    boolean tate = false;
    {
      int u = next - 5;
      int s = next + 5;
      if (0 <= u && s < 25) {
        if ((((bits >> u) & 1) ^ ((bits >> s) & 1)) == 1) {
          tate = true;
        }
      }
    }
    return !(yoko | tate);
  }

  FastScanner sc = new FastScanner(System.in);

  public static void main(String[] args) {
    new Main().run();
  }

  int ni() {
    return Integer.parseInt(sc.next());
  }

  void debug(Object... os) {
    System.err.println(Arrays.deepToString(os));
  }

  class BIT<T> {
    int n;
    ArrayList<T> bit;
    BiFunction<T, T, T> bif;

    /**
     * 1-indexed なBinary Indexed Treeを構築する
     *
     * @param n   容量
     * @param bif 適用させる関数
     * @param sup 初期値
     */
    BIT(int n, BiFunction<T, T, T> bif, Supplier<T> sup) {
      this.n = n;
      bit = new ArrayList<>(n + 1);
      for (int i = 0; i < n + 1; ++i) {
        bit.add(sup.get());
      }
      this.bif = bif;
    }

    /**
     * iの位置の値をvで更新する
     *
     * @param i index
     * @param v 新しい値
     */
    void set(int i, T v) {
      for (int x = i; x <= n; x += x & -x) {
        bit.set(x, bif.apply(bit.get(x), v));
      }
    }

    /**
     * クエリー
     *
     * @param defaultValue 初期値
     * @param i            index
     * @return [1, i]までfを適用した結果
     */
    T reduce(T defaultValue, int i) {
      T ret = defaultValue;
      for (int x = i; x > 0; x -= x & -x) {
        ret = bif.apply(ret, bit.get(x));
      }
      return ret;
    }
  }

  class SegmentTree<T> {
    int n;
    ArrayList<T> dat;
    BiFunction<T, T, T> bif;
    Supplier<T> sup;

    /**
     * 0-indexed なSegment Treeを構築する
     *
     * @param n_  要求容量
     * @param bif 適用させる関数
     * @param sup 初期値
     */
    SegmentTree(int n_, BiFunction<T, T, T> bif, Supplier<T> sup) {
      n = 1;
      while (n < n_) n *= 2;

      dat = new ArrayList<>(2 * n - 1);
      for (int i = 0; i < 2 * n - 1; ++i) {
        dat.add(sup.get());
      }
      this.bif = bif;
      this.sup = sup;
    }

    /**
     * kの位置の値をvで更新する
     *
     * @param k index
     * @param v 新しい値
     */
    void set(int k, T v) {
      k += n - 1;
      dat.set(k, v);
      while (k > 0) {
        k = (k - 1) / 2;
        dat.set(k, bif.apply(dat.get(k * 2 + 1), dat.get(k * 2 + 2)));
      }
    }

    /**
     * クエリー
     *
     * @param l はじめ
     * @param r おわり
     * @return [l, r)での演算bifを適用した結果を返す
     */
    T reduce(int l, int r) {
      return _reduce(l, r, 0, 0, n);
    }

    T _reduce(int a, int b, int k, int l, int r) {
      if (r <= a || b <= l) return sup.get();
      if (a <= l && r <= b) return dat.get(k);
      T vl = _reduce(a, b, k * 2 + 1, l, (l + r) / 2);
      T vr = _reduce(a, b, k * 2 + 2, (l + r) / 2, r);
      return bif.apply(vl, vr);
    }
  }

  class Pair<F extends Comparable<F>, S extends Comparable<S>> implements Comparable<Pair<F, S>> {
    F f;
    S s;

    Pair() {
    }

    Pair(F f, S s) {
      this.f = f;
      this.s = s;
    }

    Pair(Pair<F, S> p) {
      f = p.f;
      s = p.s;
    }

    @Override
    public int compareTo(Pair<F, S> p) {
      if (f.compareTo(p.f) != 0) {
        return f.compareTo(p.f);
      }
      return s.compareTo(p.s);
    }

    @Override
    public int hashCode() {
      return f.hashCode() ^ s.hashCode();
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (o == null || this.f == null || this.s == null) {
        return false;
      }
      if (this.getClass() != o.getClass()) {
        return false;
      }
      Pair p = (Pair) o;
      return this.f.equals(p.f) && this.s.equals(p.s);
    }

    @Override
    public String toString() {
      return "{" + f.toString() + ", " + s.toString() + "}";
    }
  }

  /**
   * ユークリッドの互除法
   *
   * @return a と b の最大公約数
   */
  long gcd(long a, long b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }

  /**
   * 拡張ユークリッドの互除法
   *
   * @return mx + ny = gcd(m, n)となるような(x, y)を返す
   */
  Pair<Long, Long> gcd_ex(long m, long n) {
    long[][] mat = _gcd_ex(m, n);
    return new Pair<>(mat[0][0], mat[0][1]);
  }

  long[][] _gcd_ex(long m, long n) {
    if (n == 0) {
      return new long[][]{{1, 0}, {0, 1}};
    }
    long k = m / n;
    long[][] K = new long[][]{{0, 1}, {1, -k}};
    long[][] r = _gcd_ex(n, m % n);
    long[][] dst = new long[2][2];
    for (int y = 0; y < 2; ++y)
      for (int x = 0; x < 2; ++x)
        for (int i = 0; i < 2; ++i)
          dst[y][x] += r[y][i] * K[i][x];
    return dst;
  }

  long MOD = 1_000_000_007;

  /**
   * 繰り返し2乗法を用いたべき乗の実装
   *
   * @return a^r (mod 1,000,000,007)
   */
  long pow(long a, long r) {
    long sum = 1;
    while (r > 0) {
      if ((r & 1) == 1) {
        sum *= a;
        sum %= MOD;
      }
      a *= a;
      a %= MOD;
      r >>= 1;
    }
    return sum;
  }

  /**
   * 組み合わせ
   * O(n)
   *
   * @return {}_nC_r
   */
  long C(int n, int r) {
    long sum = 1;
    for (int i = n; 0 < i; --i) {
      sum *= i;
      sum %= MOD;
    }
    long s = 1;
    for (int i = r; 0 < i; --i) {
      s *= i;
      s %= MOD;
    }
    sum *= pow(s, MOD - 2);
    sum %= MOD;

    long t = 1;
    for (int i = n - r; 0 < i; --i) {
      t *= i;
      t %= MOD;
    }
    sum *= pow(t, MOD - 2);
    sum %= MOD;

    return sum;
  }

  double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;

  /**
   * 黄金分割探索
   *
   * @param left  下限
   * @param right 上限
   * @param f     探索する関数
   * @param comp  上に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue)
   *              下に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue).reversed()
   * @return 極値の座標x
   */
  double goldenSectionSearch(double left, double right, Function<Double, Double> f, Comparator<Double> comp) {
    double c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
    double c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
    double d1 = f.apply(c1);
    double d2 = f.apply(c2);
    while (right - left > 1e-9) {
      if (comp.compare(d1, d2) > 0) {
        right = c2;
        c2 = c1;
        d2 = d1;
        c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
        d1 = f.apply(c1);
      } else {
        left = c1;
        c1 = c2;
        d1 = d2;
        c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
        d2 = f.apply(c2);
      }
    }
    return right;
  }

  /**
   * [a,b]をm:nに内分する点を返す
   */
  double divideInternally(double a, double b, double m, double n) {
    return (n * a + m * b) / (m + n);
  }

  /**
   * http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b
   */
  static class FastScanner {
    private final InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    public FastScanner(InputStream in) {
      this.in = in;
    }

    private boolean hasNextByte() {
      if (ptr < buflen) {
        return true;
      } else {
        ptr = 0;
        try {
          buflen = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (buflen <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    public boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    public long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }
  }
}

Submission Info

Submission Time
Task D - 25個の整数
User arukuka
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 12205 Byte
Status AC
Exec Time 1075 ms
Memory 190660 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 4
AC × 19
AC × 29
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Subtask1 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt
Subtask2 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt, test-2-01.txt, test-2-02.txt, test-2-03.txt, test-2-04.txt, test-2-05.txt, test-2-06.txt, test-2-07.txt, test-2-08.txt, test-2-09.txt, test-2-10.txt
Case Name Status Exec Time Memory
sample-01.txt AC 446 ms 186992 KB
sample-02.txt AC 410 ms 187056 KB
sample-03.txt AC 464 ms 190128 KB
sample-04.txt AC 409 ms 186920 KB
test-1-01.txt AC 434 ms 187896 KB
test-1-02.txt AC 414 ms 187000 KB
test-1-03.txt AC 416 ms 186900 KB
test-1-04.txt AC 409 ms 186980 KB
test-1-05.txt AC 422 ms 188112 KB
test-1-06.txt AC 425 ms 187240 KB
test-1-07.txt AC 412 ms 186960 KB
test-1-08.txt AC 417 ms 187252 KB
test-1-09.txt AC 417 ms 187276 KB
test-1-10.txt AC 410 ms 186800 KB
test-1-11.txt AC 418 ms 186836 KB
test-1-12.txt AC 426 ms 187044 KB
test-1-13.txt AC 411 ms 186968 KB
test-1-14.txt AC 414 ms 186984 KB
test-1-15.txt AC 411 ms 186956 KB
test-2-01.txt AC 475 ms 190444 KB
test-2-02.txt AC 421 ms 187520 KB
test-2-03.txt AC 436 ms 189216 KB
test-2-04.txt AC 490 ms 189980 KB
test-2-05.txt AC 440 ms 188948 KB
test-2-06.txt AC 615 ms 190612 KB
test-2-07.txt AC 1075 ms 189248 KB
test-2-08.txt AC 726 ms 189980 KB
test-2-09.txt AC 689 ms 190624 KB
test-2-10.txt AC 638 ms 190660 KB