結果

問題 No.12 限定された素数
ユーザー ゆうきゆうき
提出日時 2022-10-23 04:20:02
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,543 ms / 5,000 ms
コード長 6,066 bytes
コンパイル時間 3,697 ms
コンパイル使用メモリ 89,120 KB
実行使用メモリ 79,492 KB
最終ジャッジ日時 2023-09-14 18:04:37
合計ジャッジ時間 45,351 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,526 ms
75,472 KB
testcase_01 AC 1,524 ms
75,548 KB
testcase_02 AC 1,513 ms
75,944 KB
testcase_03 AC 1,515 ms
74,404 KB
testcase_04 AC 1,528 ms
75,944 KB
testcase_05 AC 1,533 ms
76,128 KB
testcase_06 AC 1,538 ms
75,256 KB
testcase_07 AC 1,536 ms
75,748 KB
testcase_08 AC 1,532 ms
75,816 KB
testcase_09 AC 1,539 ms
75,548 KB
testcase_10 AC 1,532 ms
75,604 KB
testcase_11 AC 1,535 ms
75,432 KB
testcase_12 AC 1,539 ms
75,528 KB
testcase_13 AC 1,543 ms
75,532 KB
testcase_14 AC 1,538 ms
75,620 KB
testcase_15 AC 1,533 ms
79,492 KB
testcase_16 AC 1,537 ms
75,952 KB
testcase_17 AC 1,521 ms
75,348 KB
testcase_18 AC 1,525 ms
75,216 KB
testcase_19 AC 1,514 ms
75,944 KB
testcase_20 AC 1,518 ms
75,396 KB
testcase_21 AC 1,521 ms
75,932 KB
testcase_22 AC 1,516 ms
75,648 KB
testcase_23 AC 1,523 ms
75,512 KB
testcase_24 AC 1,515 ms
75,284 KB
testcase_25 AC 1,517 ms
75,936 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.lang.management.ManagementFactory;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.function.IntFunction;

class Main{
  boolean isDebug = ManagementFactory.getRuntimeMXBean().getInputArguments().toString()
      .contains("-agentlib:jdwp");
  final MyReader in = new MyReader(System.in);
  final MyWriter out = new MyWriter(System.out);

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

  private void exe(){
    input();
    preCalc();
    solve();
    out.flush();
  }

  int N = in.it();
  int[] A = in.it(N);

  private void input(){}

  private void preCalc(){}

  boolean[] allowed = new boolean[10];
  boolean[] used = new boolean[10];

  void solve(){
    for (var a:A)
      allowed[a] = true;

    int ans = -1;
    int last = 1;

    for (var p:primes(5000000))
      if (ng(p)) {
        if (clear())
          ans = Math.max(ans,p -1 -last);
        if (ans == 0)
          System.out.println();
        last = p +1;
        used = new boolean[10];
      } else
        updUsed(p);

    if (clear())
      ans = Math.max(ans,5000000  -last);

    out.println(ans);
  }

  private boolean clear(){
    for (int i = 0;i < 10;i++)
      if (allowed[i] && !used[i])
        return false;

    return true;
  }

  private void updUsed(int p){
    while (0 < p) {
      used[p %10] = true;
      p /= 10;
    }
  }

  private boolean ng(int p){

    while (0 < p) {
      if (!allowed[p %10])
        return true;
      p /= 10;
    }

    return false;
  }

  Set<Integer> primes(final int bound){
    Set<Integer> ret = new LinkedHashSet<>();
    for (int i = 2;i <= bound;i++) {
      boolean flg = true;
      for (final int p:ret)
        if (i %p == 0) {
          flg = false;
          break;
        } else if (i < p *p)
          break;
      if (flg)
        ret.add(i);
    }
    return ret;
  }

  /* 定数 */
  //  final static int mod = (int) 1e9 +7;
  final static int mod = 998244353;
  final static String yes = "Yes";
  final static String no = "No";

  /* 入力 */
  static class MyReader{
    byte[] buf = new byte[1 <<16];
    int head = 0;
    int tail = 0;
    InputStream in;

    public MyReader(final InputStream in){ this.in = in; }

    byte read(){
      if (head == tail) {
        try {
          tail = in.read(buf);
        } catch (IOException e) {
          e.printStackTrace();
        }
        head = 0;
      }
      return buf[head++];
    }

    boolean isPrintable(final byte c){ return 32 < c && c < 127; }

    boolean isNum(final byte c){ return 47 < c && c < 58; }

    byte nextPrintable(){
      byte ret = read();
      return isPrintable(ret) ? ret : nextPrintable();
    }

    int it(){ return (int) lg(); }

    int[] it(final int N){
      int[] a = new int[N];
      Arrays.setAll(a,i -> it());
      return a;
    }

    int[][] it(final int H,final int W){ return arr(new int[H][],i -> it(W)); }

    int idx(){ return it() -1; }

    int[] idx(final int N){
      int[] a = new int[N];
      Arrays.setAll(a,i -> idx());
      return a;
    }

    int[][] idx(final int H,final int W){ return arr(new int[H][],i -> idx(W)); }

    long lg(){
      byte i = nextPrintable();
      boolean negative = i == 45;
      long n = negative ? 0 : i -'0';
      while (isPrintable(i = read()))
        n = 10 *n +i -'0';
      return negative ? -n : n;
    }

    long[] lg(final int N){
      long[] a = new long[N];
      Arrays.setAll(a,i -> lg());
      return a;
    }

    long[][] lg(final int H,final int W){ return arr(new long[H][],i -> lg(W)); }

    char[] ch(){ return str().toCharArray(); }

    char[][] ch(final int H){ return arr(new char[H][],i -> ch()); }

    String line(){
      StringBuilder sb = new StringBuilder();

      byte c;
      while (isPrintable(c = read()) || c == ' ')
        sb.append((char) c);
      return sb.toString();
    }

    String str(){
      StringBuilder sb = new StringBuilder();
      sb.append((char) nextPrintable());
      byte c;
      while (isPrintable(c = read()))
        sb.append((char) c);
      return sb.toString();
    }

    String[] str(final int N){ return arr(new String[N],i -> str()); }

    <T> T[] arr(final T[] arr,final IntFunction<T> f){
      Arrays.setAll(arr,f);
      return arr;
    }
  }

  /* 出力 */
  static class MyWriter{
    OutputStream out;

    byte[] buf = new byte[1 <<16];
    byte[] ibuf = new byte[20];

    int tail = 0;

    public MyWriter(final OutputStream out){ this.out = out; }

    void flush(){
      try {
        out.write(buf,0,tail);
        tail = 0;
      } catch (IOException e) {
        e.printStackTrace();
      }
    }

    void sp(){ write((byte) ' '); }

    void ln(){ write((byte) '\n'); }

    void write(final byte b){
      buf[tail++] = b;
      if (tail == buf.length)
        flush();
    }

    void write(final byte[] b,final int off,final int len){
      for (int i = off;i < off +len;i++)
        write(b[i]);
    }

    void write(long n){
      if (n < 0) {
        n = -n;
        write((byte) '-');
      }

      int i = ibuf.length;
      do {
        ibuf[--i] = (byte) (n %10 +'0');
        n /= 10;
      } while (n > 0);

      write(ibuf,i,ibuf.length -i);
    }

    void println(final boolean b){ println(b ? yes : no); }

    void println(final long n){
      write(n);
      ln();
    }

    public void println(final double d){ println(String.valueOf(d)); }

    void println(final String s){
      for (byte b:s.getBytes())
        write(b);
      ln();
    }

    public void println(final char[] s){
      for (char b:s)
        write((byte) b);
      ln();
    }

    void println(final int[] a){
      for (int i = 0;i < a.length;i++) {
        if (0 < i)
          sp();
        write(a[i]);
      }
      ln();
    }

    void println(final long[] a){
      for (int i = 0;i < a.length;i++) {
        if (0 < i)
          sp();
        write(a[i]);
      }
      ln();
    }

  }
}
0